AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_direction_determinate

def

A is direction-determinate: some d : Q → {left, right} gives the direction of every defined transition from the state it enters, endmarker transitions included.

Statement

def two_way_dfa_direction_determinate {σ 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.1: direction-determinate sources
Verified
23 Oct 2026
Axioms
none listed
Built on 1
  • two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…

Lean source view module on GitHub

def two_way_dfa_direction_determinate {σ Q : Type*} (A : two_way_dfa σ Q) : Prop :=
  ∃ d : Q → Bool, (∀ p a q e, A.δ p a = some (q, e) → e = d q) ∧
    (∀ p q, A.δL p = some q → d q = true) ∧ (∀ p q, A.δR p = some q → d q = false)
See it in the graphDiscuss this resultChallenge it