Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
Bruno Guillon, Luca Prigioniero, Taheri, Javad · arXiv (Cornell University) · 2025
We prove that, paying a polynomial increase in size only, every unrestricted two-way nondeterministic finite automaton (2NFA) can be complemented by a 1-limited automaton (1-LA), a nondeterministic extension of 2NFAs still characterizing regular languages. The resulting machine is actually a restricted form of 1-LAs - known as 2NFAs with common guess - and is self-verifying. A corollary of our construction is that a single exponential is necessary and sufficient for complementing 1-LAs.