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; viliam.geffert@upjs.sk; lubomira.istonova@upjs.sk

Received: 8 September 2009
Accepted: 21 December 2010

Abstract

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.