AFTD Auto-Formalizing Theoretical Domains

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

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