Two-way deterministic finite automata are exponentially more succinct than sweeping automata

DOI10.1016/0020-0190(81)90012-0zbMath0471.68039OpenAlexW2085151919MaRDI QIDQ1157965

Silvio Micali

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

zbMATH Keywords

complexitynondeterminismsize of description

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Nondeterminism and the size of two way finite automata
• Unnamed Item

This page was built for publication: Two-way deterministic finite automata are exponentially more succinct than sweeping automata