Nondeterminism is essential in small two-way finite automata with few reversals

DOI10.1016/j.ic.2012.11.001zbMath1267.68135OpenAlexW2041850079MaRDI QIDQ1951583

Christos A. Kapoutsis

Publication date: 6 June 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.11.001

zbMATH Keywords

nondeterminismtwo-way finite automatareversals

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Two-way automata making choices only at the endmarkers ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ New size hierarchies for two way automata ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines

This page was built for publication: Nondeterminism is essential in small two-way finite automata with few reversals