two_way_dfa_halting
def
A is halting: on every input its computation stops, by an undefined transition or by reaching the accepting configuration (f, 0).
Statement
def two_way_dfa_halting {σ Q : Type*} (A : two_way_dfa σ Q) : Prop
- Defined in
- arXiv:2610.18897 (A factor-two lower bound for complementing two-way deterministic finite automata), Section 7: a halting recognizer
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 2
- two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…
- two_way_dfa_runThe configuration after t steps of the computation from (s, 0) on w, or none once it has halted on an undefined transition.
- Used by 1
- two_way_dfa_halting_emptySanity: a two-state automaton with no transitions and s ≠ f halts on every input.
Lean source view module on GitHub
def two_way_dfa_halting {σ Q : Type*} (A : two_way_dfa σ Q) : Prop := ∀ w, ∃ t, two_way_dfa_run A w t = none ∨ two_way_dfa_run A w t = some (A.f, 0)