Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata

2025/07/15 by Bruno Guillon, Guillon, Bruno, Luca Prigioniero +3 · 1 voice
Computer Science · #68Q45 #F.1.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL

paper · pdf · doi:10.48550/arxiv.2507.11209

Abstract

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.

Citations

• Nondeterminism makes unary 1-limited automata concise
• Two-Way Automata Making Choices Only at the Endmarkers

Discussions

• Bruno Guillon, Luca Prigioniero, Javad Taheri: Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata https://arxiv.org/abs/2507.11209 https://arxiv.org/pdf/2507.11 [bsky, 0 points, 0 comments]

Related

• Nondeterminism makes unary 1-limited automata concise
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)
• A quadratic lower bound for 2DFAs against one-way liveness
• Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines