AFTD Auto-Formalizing Theoretical Domains

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}
See it in the graphDiscuss this resultChallenge it