Nondeterminism makes unary 1-limited automata concise

We investigate the descriptional complexity of 1-limited automata (1-LAs) in the unary case. These machines characterize regular languages and are two-way finite automata (2NFAs) extended to allow rewriting each tape cell upon its first visit. We prove exponential lower bounds for the simulations of 1-LAs by deterministic 1-LAs and 2NFAs. These results are derived from a doubly exponential lower bound for the simulation of 1-LAs by one-way deterministic finite automata (1DFAs), and close a question left open in [Pighizzini and Prigioniero. Limited automata and unary languages. Inf. Comput., 266:60–74]. Our results hold even when, besides being unary, the 1-la is a 2DFA with common-guess (2DFA+cg), namely a 1-la restricted to use nondeterminism only to annotate the tape cells during a write-only initial phase, before performing a read-only deterministic computation.<p></p>