AFTD Auto-Formalizing Theoretical Domains

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

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