RAIRO-Theor. Inf. Appl.
Volume 44, Number 4, October-December 2010
|Page(s)||507 - 523|
|Published online||28 February 2011|
Translation from classical two-way automata to pebble two-way automata
Department of Computer Science,
P. J. Šafárik University,
Jesenná 5, 040 01 Košice, Slovakia;
Accepted: 21 December 2010
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles. However, we show that these two machine models are not independent: if there exists a polynomial trade-off for the classical two-way automata, then, for each ≥ 0, there must also exist a polynomial trade-off for the two-way automata with nested pebbles. Thus, we have an upward collapse (or a downward separation) from the classical two-way automata to more powerful pebble automata, still staying within the class of regular languages. The same upward collapse holds for complementation of nondeterministic two-way machines. These results are obtained by showing that each pebble machine can be, by using suitable inputs, simulated by a classical two-way automaton (and vice versa), with only a linear number of states, despite the existing exponential blow-up between the classical and pebble two-way machines.
Mathematics Subject Classification: 68Q45 / 68Q70
Key words: Finite automata / regular languages / descriptional complexity
© EDP Sciences, 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.