AFTD Auto-Formalizing Theoretical Domains

list_longest_suffix_mem

def

For a finite set B of words containing the empty word and any word u, the longest element of B that is a suffix of u.

Statement

noncomputable def list_longest_suffix_mem {α : Type*} [DecidableEq α]
    (B : Finset (List α)) (h0 : ([] : List α) ∈ B) (u : List α) : List α
Source
step towards op_1716_sequential_subset_sync_sharp_k_approximation
Verified
15 Nov 2026
Axioms
none listed

Lean source view module on GitHub

/-- The longest member of B that is a suffix of u, chosen noncomputably. -/
noncomputable def list_longest_suffix_mem {α : Type*} [DecidableEq α]
    (B : Finset (List α)) (h0 : ([] : List α) ∈ B) (u : List α) : List α := Classical.choose (p := fun s : List α =>
      s ∈ B ∧ s <:+ u ∧ ∀ t : List α, t ∈ B → t <:+ u → t.length ≤ s.length) (by
    have hne : (B.filter (fun t => t <:+ u)).Nonempty :=
      ⟨[], Finset.mem_filter.mpr ⟨h0, List.nil_suffix⟩⟩
    obtain ⟨s, hs, hmax⟩ := Finset.exists_max_image _ (fun t : List α => t.length) hne
    obtain ⟨hsB, hsu⟩ := Finset.mem_filter.mp hs
    exact ⟨s, hsB, hsu, fun t ht htu => hmax t (Finset.mem_filter.mpr ⟨ht, htu⟩)⟩)
See it in the graphDiscuss this resultChallenge it