Hromkovič, Juraj; Schnitger, Georg Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation. (English) Zbl 1039.68068 Baeten, Jos C. M. (ed.) et al., Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40493-7/pbk). Lect. Notes Comput. Sci. 2719, 439-451 (2003). Summary: Whether there exists an exponential gap between the size of a minimal deterministic two-way automaton and the size of a minimal nondeterministic two-way automaton for a specific regular language is a long standing open problem and surely one of the most challenging problems in automata theory. Twenty four years ago M. Sipser [“Lower bounds on the size of sweeping automata”, J. Comput. Syst. Sci. 21, 195–202 (1980; Zbl 0445.68064)] showed an exponential gap between nondeterminism and determinism for the so-called sweeping automata which are automata whose head can reverse direction only at the endmarkers. Sweeping automata can be viewed as a special case of oblivious two-way automata with a number of reversals bounded by a constant.Our first result extends the result of Sipser to general oblivious two-way automata with an unbounded number of reversals. Using this extension we show our second result, namely an exponential gap between determinism and nondeterminism for two-way automata with the degree of non-obliviousness bounded by \(o(n)\) for inputs of length \(n\). The degree of non-obliviousness of a two-way automaton is the number of distinct orders in which the tape cells are visited.For the entire collection see [Zbl 1029.00041]. Cited in 14 Documents MSC: 68Q45 Formal languages and automata 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) Keywords:Finite automata; nondeterminism; descriptional complexity of regular languages Citations:Zbl 0445.68064 PDFBibTeX XMLCite \textit{J. Hromkovič} and \textit{G. Schnitger}, Lect. Notes Comput. Sci. 2719, 439--451 (2003; Zbl 1039.68068) Full Text: Link