Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal

DOI10.1016/J.IPL.2010.03.008zbMath1229.68047OpenAlexW1970263278MaRDI QIDQ656586

Marcin Balcerzak, Damian Niwinski

Publication date: 18 January 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.03.008

zbMATH Keywords

formal languagesregular languagestwo-way finite automatabounded number of reversals

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fooling a two-way nondeterministic multihead automaton with reversal number restriction
• Lower bounds on the size of sweeping automata
• Nondeterminism and the size of two way finite automata

This page was built for publication: Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal