On the Size Complexity of Rotating and Sweeping Automata

DOI10.1007/978-3-540-85780-8_36MaRDI QIDQ3533032zbMATH OpenOpenAlexFDO

Authors Richard Královič, Tobias Mömke, Christos 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)

Recommendations

• Size complexity of rotating and sweeping automata
• Tight lower bounds on the size of sweeping automata
• Lower bounds on the size of sweeping automata
• A technique for proving lower bounds on the size of sweeping automata
• scientific article; zbMATH DE number 1502106

Cites work

• An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
• Complementing two-way finite automata
• scientific article; zbMATH DE number 3754072 (Why is no real title available?)
• Lower bounds on the size of sweeping automata
• Nondeterminism and the size of two way finite automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata

Cited in

(5)

• On a compact encoding of the swap automaton
• Size Complexity of Two-Way Finite Automata
• Size complexity of rotating and sweeping automata
• A technique for proving lower bounds on the size of sweeping automata
• On the size of Boyer-Moore automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533032)