Translation from classical two-way automata to pebble two-way automata

Geffert, Viliam; Ištoňová, L'ubomíra

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 4, pp. 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.

[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

[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

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

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

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

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

[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

[9] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484-498. | Zbl

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

[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

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

[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

[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

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

[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

[17] Ch.A. Kapoutsis, Deterministic moles cannot solve liveness. J. Automat. Lang. Combin. 12 (2007) 215-235. | Zbl

[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

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

[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

[21] M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-125. | Zbl

[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

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

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

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

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