AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_run

def

The configuration after t steps of the computation from (s, 0) on w, or none once it has halted on an undefined transition.

Statement

def two_way_dfa_run {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (t : ℕ) : Option (Q × ℕ)
Defined in
arXiv:2610.18897 (A factor-two lower bound for complementing two-way deterministic finite automata), Section 2.1: the computation from (s, 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_stepOne step on the input w: in configuration (q, i), at position 0 (left endmarker) apply δL and move to 1, at position |w|+1 (right…
Used by 5
  • two_way_dfa_halting_emptySanity: a two-state automaton with no transitions and s ≠ f halts on every input.
  • two_way_dfa_run_succFor any two-way deterministic finite automaton A, input word w, and time t, the configuration after t + 1 computation steps is the result…
  • two_way_dfa_accepts_of_s_eq_fSanity: if the initial state is the final state, every word is accepted (at time 0).
  • two_way_dfa_acceptsA accepts w when its computation from (s, 0) reaches the configuration (f, 0) (state f on the left endmarker). Infinite computations and…
  • two_way_dfa_haltingA is halting: on every input its computation stops, by an undefined transition or by reaching the accepting configuration (f, 0).

Lean source view module on GitHub

def two_way_dfa_run {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (t : ℕ) : Option (Q × ℕ) :=
  (fun c => c.bind (two_way_dfa_step A w))^[t] (some (A.s, 0))
See it in the graphDiscuss this resultChallenge it