Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation
| |
|
Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation
Juraj Hromkovič5  and Georg Schnitger6
| (5) |
Lehrstuhl für Informatik I, Aachen University RWTH, Ahornstraße 55, 52074 Aachen, Germany |
| (6) |
Fachbereich Informatik, Johann-Wolfgang-Goethe Universität, Robert-Mayer-Straße 11-15, 60054 Frankfurt am Main, Germany |
Abstract
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.
Keywords Finite automata - nondeterminism - descriptional complexity of regular languages
Supported by DFG grants HR 1416-1 and SCHN 50312-1.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|