On the Size Complexity of Rotating and Sweeping Automata

DOI10.1007/978-3-540-85780-8_36zbMath1161.68541OpenAlexW1524385326MaRDI QIDQ3533032

Tobias Mömke, Richard Královič, Christos A. Kapoutsis

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_36

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Size complexity of rotating and sweeping automata ⋮ Size Complexity of Two-Way Finite Automata

Cites Work

• Unnamed Item
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Complementing two-way finite automata
• An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
• Nondeterminism and the size of two way finite automata

This page was built for publication: On the Size Complexity of Rotating and Sweeping Automata