min_bipartite_cactus_nfa_states
def
The minimum number of states in an epsilon-free NFA accepting L whose transition graph is a bipartite cactus.
Statement
noncomputable def min_bipartite_cactus_nfa_states {α : Type*} (L : Language α) : ℕ
- Defined in
- arXiv:2610.11717 Sec. 4
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Built on 1
- is_bipartite_cactus_nfaAn NFA A is a bipartite cactus automaton if its undirected transition graph is a cactus and 2-colorable.
- Used by 1
- min_bipartite_cactus_nfa_states_emptyThe empty language over any alphabet has a bipartite cactus NFA with at most one state.
Read back from the Lean
For a type α and a language L : Language α (i.e., a set of lists of α), min_bipartite_cactus_nfa_states L is the infimum in ℕ of the set of all k : ℕ such that there exists a finite type σ and an NFA A with alphabet α and state type σ satisfying:
1. The cardinality of σ is k;
2. The language accepted by A is L;
3. A is a bipartite cactus NFA (is_bipartite_cactus_nfa A).
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
/-- Minimum number of states in an epsilon-free NFA accepting L whose transition graph is a bipartite cactus. -/ noncomputable def min_bipartite_cactus_nfa_states {α : Type*} (L : Language α) : ℕ := sInf { k : ℕ | ∃ (σ : Type) (_ : Fintype σ) (A : NFA α σ), Fintype.card σ = k ∧ A.accepts = L ∧ is_bipartite_cactus_nfa A }