word_generating_rank
def
The generating rank rk(X) of a finite set of words X over an alphabet α is the minimum cardinality of a generating set Y ⊆ α* such that every word in X can be formed by concatenating words from Y.
Statement
noncomputable def word_generating_rank {α : Type*} (X : Finset (List α)) : ℕ
- Defined in
- arXiv:2611.15074 Definition 2.5
- Verified
- 15 Nov 2026
- Axioms
- none listed
Read back from the Lean
For a type α and a finite set of lists X : Finset (List α), word_generating_rank X is defined as the infimum in ℕ (the least element) of the set of all natural numbers k for which there exists a finite set of lists Y : Finset (List α) of cardinality k such that every word w ∈ X can be written as the concatenation (L.flatten) of some list of words L : List (List α) whose elements all belong to Y.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The generating rank rk(X) of a finite set of words X is the minimum cardinality of a generating set Y such that X ⊆ Y*. -/ noncomputable def word_generating_rank {α : Type*} (X : Finset (List α)) : ℕ := sInf {k : ℕ | ∃ Y : Finset (List α), Y.card = k ∧ ∀ w ∈ X, ∃ L : List (List α), w = L.flatten ∧ ∀ y ∈ L, y ∈ Y}