DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ
From MaRDI portal
Publication:5495414
DOI10.1142/S012905411340025XzbMath1293.68188OpenAlexW2019422882MaRDI QIDQ5495414
Juraj Hromkovič, Richard Královič, Rastislav Královič, Richard Štefanec
Publication date: 4 August 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s012905411340025x
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Optimal 2DFA Algorithms for One-Way Liveness on Two and Three Symbols ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem
Cites Work
- Size complexity of rotating and sweeping automata
- Two-way unary automata versus logarithmic space
- Finite automata and unary languages
- Lower bounds on the size of sweeping automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
- Converting two-way nondeterministic unary automata into simpler automata.
- The power of nondeterminism and randomness for oblivious branching programs
- Magic numbers in the state hierarchy of finite automata
- Complementing two-way finite automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
