AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_accepts

def

A accepts w when its computation from (s, 0) reaches the configuration (f, 0) (state f on the left endmarker). Infinite computations and halting elsewhere reject.

Statement

def two_way_dfa_accepts {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) : Prop
Defined in
arXiv:2610.18897 (A factor-two lower bound for complementing two-way deterministic finite automata), Section 2.1: acceptance exactly upon reaching (f, 0)
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

Lean source view module on GitHub

def two_way_dfa_accepts {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) : Prop :=
  ∃ t, two_way_dfa_run A w t = some (A.f, 0)
See it in the graphDiscuss this resultChallenge it