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.
@article{ITA_2010__44_4_507_0,
author = {Geffert, Viliam and I\v sto\v nov\'a, L'ubom\'\i ra},
title = {Translation from classical two-way automata to pebble two-way automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {44},
year = {2010},
pages = {507-523},
doi = {10.1051/ita/2011001},
mrnumber = {2775409},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2010__44_4_507_0}
}
Geffert, Viliam; Ištoňová, L'ubomíra. Translation from classical two-way automata to pebble two-way automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 507-523. doi : 10.1051/ita/2011001. http://gdmltest.u-ga.fr/item/ITA_2010__44_4_507_0/
[1] and , On the complexity of regular languages in terms of finite automata. Tech. Rep., Vol. 304, Polish Academy of Sciences (1977). | Zbl 0364.68057
[2] and , Automata on a 2-dimensional tape, in Proc. IEEE Symp. Switching Automata Theory (1967), 155-160.
[3] , A History of Mathematics. John Wiley & Sons (1968). | Zbl 0698.01001
[4] , , and , On pebble automata. Theoret. Comput. Sci. 44 (1986) 111-121. | Zbl 0612.68045
[5] , and , Space bounded computations: Review and new separation results. Theoret. Comput. Sci. 80 (1991) 289-302. | Zbl 0745.68051
[6] , Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-158. (Corrigendum: Theoret. Comput. Sci. 302 (2003) 497-498). | Zbl 0638.68096
[7] and , Prime Numbers. John Wiley & Sons (1985). | Zbl 0624.10001
[8] and , Tree-walking pebble automata, in Jewels Are Forever, Contributions to Theoretical Computer Science in Honor of Arto Salomaa, J. Karhumäki, H. Maurer, G. Păun and G. Rozenberg, Eds. Springer-Verlag (1999), 72-83. | Zbl 0944.68108
[9] , Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484-498. | Zbl 0762.68022
[10] , Bridging across the space frontier. Inform. Comput. 142 (1998) 127-158. | Zbl 0917.68077
[11] , and , Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci. 295 (2003) 189-203. | Zbl 1045.68080
[12] , and , Complementing two-way finite automata. Inform. Comput. 205 (2007) 1173-1187. | Zbl 1121.68063
[13] and , Complexity results for two-way and multi-pebble automata and their logics. Theoret. Comput. Sci. 169 (1996) 161-184. | Zbl 0874.68213
[14] , and , Hierarchies of memory limited computations, in IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965), 179-190. | Zbl 0229.02033
[15] , and , Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001). | Zbl 0980.68066
[16] and , Nondeterminism versus determinism for two-way nondeterministic automata: Generalizations of Sipser's separation, in Proc. Internat. Colloq. Automata, Languages and Programming. Lect. Notes Comput. Sci. 2719 (2003) 439-451. | Zbl 1039.68068
[17] , Deterministic moles cannot solve liveness. J. Automat. Lang. Combin. 12 (2007) 215-235. | Zbl 1145.68461
[18] , Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik Akademie-Verlag, Berlin, in German, Vol. 6, 329-335 (1966). | Zbl 0168.25902
[19] and , Optimal simulations between unary automata. SIAM J. Comput. 30 (2001) 1976-1992. | Zbl 0980.68048
[20] , On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. C-20 (1971) 1211-1214. | Zbl 0229.94033
[21] and , Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-125. | Zbl 0158.25404
[22] and , Nondeterminism and the size of two-way finite automata, in Proc. ACM Symp. Theory Comput. (1978), 275-286.
[23] , and , On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320 (2004) 315-329. | Zbl 1068.68078
[24] , The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198-200. | Zbl 0158.25601
[25] , Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360-364. | Zbl 0445.68064
[26] , Halting space bounded computations. Theoret. Comput. Sci. 10 (1980) 335-338. | Zbl 0423.68011
[27] , Turing Machines with Sublogarithmic Space. Lect. Notes Comput. Sci. 843 (1994). | Zbl 0998.68062