is_bipartite_cactus_nfa
def
An NFA A is a bipartite cactus automaton if its undirected transition graph is a cactus and 2-colorable.
Statement
def is_bipartite_cactus_nfa {α σ : Type*} (A : NFA α σ) : Prop
- Defined in
- arXiv:2610.11717 Thm 1.1
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Built on 2
- nfa_transition_graphThe transition graph of an NFA A has an undirected edge between distinct states u and v if there is a transition from u to v or from v to…
- simple_graph_is_cactusA simple graph is a cactus if any two simple cycles that share an edge have identical edge sets (every edge belongs to at most one simple…
- Used by 2
- min_bipartite_cactus_nfa_statesThe minimum number of states in an epsilon-free NFA accepting L whose transition graph is a bipartite cactus.
- 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 nondeterministic finite automaton A : NFA α σ with alphabet α and state type σ, is_bipartite_cactus_nfa A asserts that the undirected transition graph of A is both a cactus graph (any two cycles that share an edge are the same cycle as subgraphs) and 2-colorable (bipartite).
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
/-- Predicate asserting that an NFA has a bipartite cactus transition graph. -/ def is_bipartite_cactus_nfa {α σ : Type*} (A : NFA α σ) : Prop := simple_graph_is_cactus (nfa_transition_graph A) ∧ (nfa_transition_graph A).Colorable 2