×

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].

MSC:

68Q45 Formal languages and automata
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Citations:

Zbl 0445.68064
PDFBibTeX XMLCite
Full Text: Link