2025/07/15 by Guillon, Bruno, Prigioniero, Luca, Taheri, Javad
#68Q45 #F.1.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2507.11209
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.