generatingRank
def
The generating rank rk(X) of a finite set of words X is the minimum cardinality of a generating set Y such that X is contained in the Kleene star of Y.
Statement
noncomputable def generatingRank {α : 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 X : Finset (List α) of lists over α, generatingRank X is the infimum in ℕ (sInf) of the set of natural numbers n such that there exists a finite set Y : Finset (List α) of cardinality n with the property that every element w ∈ X can be written as the concatenation (L.flatten) of some list of lists 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 of a finite set of words X over an alphabet α is the minimum cardinality of a set Y such that every word in X is formed by concatenating words from Y. -/ noncomputable def generatingRank {α : Type*} (X : Finset (List α)) : ℕ := sInf { n : ℕ | ∃ Y : Finset (List α), Y.card = n ∧ ∀ w ∈ X, ∃ L : List (List α), w = L.flatten ∧ ∀ y ∈ L, y ∈ Y }