AFTD Auto-Formalizing Theoretical Domains

nfa_complies_ida

def

An NFA complies with IDA if there exist distinct states p and q and a word v such that p is reachable from p by v, q is reachable from p by v, and q is reachable from q by v.

Statement

def nfa_complies_ida {α σ : Type*} (M : NFA α σ) : Prop
Source
step towards finitely_ambiguous_nfa_pell_lower_bound
Verified
19 Oct 2026
Axioms
none listed
Used by 1
  • pell_nfa_no_idaThe Pell automaton A_n does not comply with IDA: there are no distinct states p, q and no word v such that p is reachable from p by v, q…

Lean source view module on GitHub

/-- The IDA property of Weber and Seidl: p -v→ p -v→ q -v→ q for a single word v, read here as reachability by one word. -/
def nfa_complies_ida {α σ : Type*} (M : NFA α σ) : Prop := ∃ p q : σ, p ≠ q ∧ ∃ v : List α,
    p ∈ M.evalFrom {p} v ∧ q ∈ M.evalFrom {p} v ∧ q ∈ M.evalFrom {q} v
See it in the graphDiscuss this resultChallenge it