Small Sweeping 2NFAs Are Not Closed Under Complement

DOI10.1007/11786986_14MaRDI QIDQ3613756zbMATH OpenOpenAlexFDO

Authors Christos Kapoutsis

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_14

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Developments in Language Theory
• Complementing two-way finite automata
• Tight lower bounds on the size of sweeping automata
• Complement for two-way alternating automata
• Lower bounds on the size of sweeping automata

Cited in

(6)

• Tight lower bounds on the size of sweeping automata
• Infinite vs. finite size-bounded randomized computations
• Nondeterminism is essential in small 2FAs with few reversals
• Size Complexity of Two-Way Finite Automata
• Size complexity of rotating and sweeping automata
• Lower bounds on the size of sweeping automata

This page was built for publication: Small Sweeping 2NFAs Are Not Closed Under Complement

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