We study the relation between the standard two-way automata and
more powerful devices, namely, two-way finite automata with an
additional "pebble" movable along the input tape. 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 pebble
two-way automata. 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 there must also exist
a polynomial trade-off for the pebble two-way automata. 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 with a linear number of states (and vice versa), despite
the existing exponential blow-up between the classical and pebble
two-way machines. |