2003 | OriginalPaper | Buchkapitel
Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation
verfasst von : Juraj Hromkovič, Georg Schnitger
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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, Sipser [M. Sipser: Lower bounds on the size of sweeping automata. ACM STOC ’79, 360–364] 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.