Two-way deterministic finite automata are exponentially more succinct than sweeping automata
From MaRDI portal
Publication:1157965
DOI10.1016/0020-0190(81)90012-0zbMath0471.68039OpenAlexW2085151919MaRDI 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
Related Items (14)
On multi-partition communication complexity ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ Size complexity of rotating and sweeping automata ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Two-way deterministic finite automata are exponentially more succinct than sweeping automata ⋮ On the Size Complexity of Rotating and Sweeping Automata ⋮ Two-way automata making choices only at the endmarkers ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Two-way unary automata versus logarithmic space ⋮ On the power of Las Vegas II: Two-way finite automata ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Tight lower bounds on the size of sweeping automata
Cites Work
This page was built for publication: Two-way deterministic finite automata are exponentially more succinct than sweeping automata
