Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-07-29
EPTCS 3, 2009, pp. 131-140
Computer Science
Formal Languages and Automata Theory
Scientific paper
10.4204/EPTCS.3.12
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.
Geffert Viliam
Ištoňová Lubomíra
No associations
LandOfFree
Translation from Classical Two-Way Automata to Pebble Two-Way Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Translation from Classical Two-Way Automata to Pebble Two-Way Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Translation from Classical Two-Way Automata to Pebble Two-Way Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-521670