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)