Translation from classical two-way automata to pebble two-way automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 44 (2010) no. 4, p. 507-523

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some $\ell$ 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 $\ell$ 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 $\ell$ 0, there must also exist a polynomial trade-off for the two-way automata with $\ell$ 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.

DOI : https://doi.org/10.1051/ita/2011001
Classification:  68Q45,  68Q70
Keywords: finite automata, regular languages, descriptional complexity
@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},
publisher = {EDP-Sciences},
volume = {44},
number = {4},
year = {2010},
pages = {507-523},
doi = {10.1051/ita/2011001},
mrnumber = {2775409},
language = {en},
url = {http://www.numdam.org/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, Volume 44 (2010) no. 4, pp. 507-523. doi : 10.1051/ita/2011001. http://www.numdam.org/item/ITA_2010__44_4_507_0/

[1] J. Berman and A. Lingas, On the complexity of regular languages in terms of finite automata. Tech. Rep., Vol. 304, Polish Academy of Sciences (1977). | Zbl 0364.68057

[2] M. Blum and C. Hewitt, Automata on a 2-dimensional tape, in Proc. IEEE Symp. Switching Automata Theory (1967), 155-160.

[3] C. Boyer, A History of Mathematics. John Wiley & Sons (1968). | Zbl 0698.01001

[4] J.H. Chang, O.H. Ibarra, M.A. Palis and B. Ravikumar, On pebble automata. Theoret. Comput. Sci. 44 (1986) 111-121. | Zbl 0612.68045

[5] R. Chang, J. Hartmanis and D. Ranjan, Space bounded computations: Review and new separation results. Theoret. Comput. Sci. 80 (1991) 289-302. | Zbl 0745.68051

[6] M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-158. (Corrigendum: Theoret. Comput. Sci. 302 (2003) 497-498). | Zbl 0638.68096

[7] W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985). | Zbl 0624.10001

[8] J. Engelfriet and H.J. Hoogeboom, 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] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484-498. | Zbl 0762.68022

[10] V. Geffert, Bridging across the $log\left(n\right)$ space frontier. Inform. Comput. 142 (1998) 127-158. | Zbl 0917.68077

[11] V. Geffert, C. Mereghetti and G. Pighizzini, Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci. 295 (2003) 189-203. | Zbl 1045.68080

[12] V. Geffert, C. Mereghetti and G. Pighizzini, Complementing two-way finite automata. Inform. Comput. 205 (2007) 1173-1187. | Zbl 1121.68063

[13] N. Globerman and D. Harel, Complexity results for two-way and multi-pebble automata and their logics. Theoret. Comput. Sci. 169 (1996) 161-184. | Zbl 0874.68213

[14] J. Hartmanis, P. M. Lewis Ii and R. E. Stearns, Hierarchies of memory limited computations, in IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965), 179-190. | Zbl 0229.02033

[15] J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001). | Zbl 0980.68066

[16] J. Hromkovič and G. Schnitger, 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] Ch.A. Kapoutsis, Deterministic moles cannot solve liveness. J. Automat. Lang. Combin. 12 (2007) 215-235. | Zbl 1145.68461

[18] O.B. Lupanov, Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik Akademie-Verlag, Berlin, in German, Vol. 6, 329-335 (1966). | Zbl 0168.25902

[19] C. Mereghetti and G. Pighizzini, Optimal simulations between unary automata. SIAM J. Comput. 30 (2001) 1976-1992. | Zbl 0980.68048

[20] F. Moore, 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] M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-125. | Zbl 0158.25404

[22] W. Sakoda and M. Sipser, Nondeterminism and the size of two-way finite automata, in Proc. ACM Symp. Theory Comput. (1978), 275-286.

[23] A. Salomaa, D. Wood and S. Yu, On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320 (2004) 315-329. | Zbl 1068.68078

[24] M. Shepherdson, The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198-200. | Zbl 0158.25601

[25] M. Sipser, Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360-364. | Zbl 0445.68064

[26] M. Sipser, Halting space bounded computations. Theoret. Comput. Sci. 10 (1980) 335-338. | Zbl 0423.68011

[27] A. Szepietowski, Turing Machines with Sublogarithmic Space. Lect. Notes Comput. Sci. 843 (1994). | Zbl 0998.68062