Two-way deterministic finite automata are exponentially more succinct than sweeping automata
From MaRDI portal
Publication:1157965
DOI10.1016/0020-0190(81)90012-0zbMath0471.68039MaRDI QIDQ1157965
Publication date: 1981
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(81)90012-0
68Q45: Formal languages and automata
Related Items
On the Size of Two-Way Reasonable Automata for the Liveness Problem, DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, On the power of Las Vegas II: Two-way finite automata, Size complexity of rotating and sweeping automata, Two-way automata making choices only at the endmarkers, Two-way unary automata versus logarithmic space, Two-way deterministic finite automata are exponentially more succinct than sweeping automata, Converting two-way nondeterministic unary automata into simpler automata., Tight lower bounds on the size of sweeping automata, Communication complexity method for measuring nondeterminism in finite automata, On multi-partition communication complexity, Oblivious two-way finite automata: decidability and complexity, On the Size of Two-Way Reasonable Automata for the Liveness Problem, On the Size Complexity of Rotating and Sweeping Automata
Cites Work
