Small Sweeping 2NFAs Are Not Closed Under Complement

DOI10.1007/11786986_14zbMath1223.68068OpenAlexW1555251244MaRDI QIDQ3613756

Christos A. 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)

Related Items (5)

Infinite vs. finite size-bounded randomized computations ⋮ Size complexity of rotating and sweeping automata ⋮ Two-way automata making choices only at the endmarkers ⋮ Nondeterminism Is Essential in Small 2FAs with Few Reversals ⋮ Size Complexity of Two-Way Finite Automata

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