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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Nondeterminism Makes Unary 1-Limited Automata Concise

  • Bruno Guillon,
  • Luca Prigioniero,
  • Javad Taheri

摘要

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.