Nondeterminism Is Essential in Small 2FAs with Few Reversals

DOI10.1007/978-3-642-22012-8_15zbMath1333.68169OpenAlexW2164188497MaRDI QIDQ3012920

Christos A. Kapoutsis

Publication date: 7 July 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-22012-8_15

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

State Complexity of Kleene-Star Operations on Trees ⋮ Two-way automata versus logarithmic space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of sweeping automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Tight lower bounds on the size of sweeping automata
• Two-Way Automata versus Logarithmic Space
• Two-Way Unary Automata versus Logarithmic Space
• Small Sweeping 2NFAs Are Not Closed Under Complement
• Nondeterminism and the size of two way finite automata

This page was built for publication: Nondeterminism Is Essential in Small 2FAs with Few Reversals