Nondeterminism Makes Unary 1-Limited Automata Concise
摘要
We investigate the descriptional complexity of 1-limited automata ( \(\textsc {1}\hbox {-}\textsc {la} \textrm{s} \) ) in the unary case. These machines characterize regular languages and are two-way finite automata ( \(\textsc {2}\textsc {n}\textsc {fa} \textrm{s} \) ) extended to allow rewriting each tape cell upon its first visit. We prove exponential lower bounds for the simulations of \(\textsc {1}\hbox {-}\textsc {la} \textrm{s} \) by deterministic \(\textsc {1}\hbox {-}\textsc {la} \textrm{s} \) and \(\textsc {2}\textsc {n}\textsc {fa} \textrm{s} \) . These results are derived from a doubly exponential lower bound for the simulation of \(\textsc {1}\hbox {-}\textsc {la} \textrm{s} \) by one-way deterministic finite automata ( \(\textsc {1}\textsc {d}\textsc {fa} \textrm{s} \) ), 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 \(\textsc {2}\textsc {d}\textsc {fa}\) with common-guess ( \({\textsc {2}\textsc {d}\textsc {fa} +\textsf{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.