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

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2010)

- Volume: 44, Issue: 4, page 507-523
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGeffert, Viliam, and 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 44.4 (2010): 507-523. <http://eudml.org/doc/245613>.

@article{Geffert2010,

abstract = {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 (andvice versa), with only a linear number of states, despite the existing exponential blow-up between the classical and pebble two-way machines.},

author = {Geffert, Viliam, Ištoňová, L'ubomíra},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {finite automata; regular languages; descriptional complexity},

language = {eng},

number = {4},

pages = {507-523},

publisher = {EDP-Sciences},

title = {Translation from classical two-way automata to pebble two-way automata},

url = {http://eudml.org/doc/245613},

volume = {44},

year = {2010},

}

TY - JOUR

AU - Geffert, Viliam

AU - Ištoňová, L'ubomíra

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

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2010

PB - EDP-Sciences

VL - 44

IS - 4

SP - 507

EP - 523

AB - 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 (andvice versa), with only a linear number of states, despite the existing exponential blow-up between the classical and pebble two-way machines.

LA - eng

KW - finite automata; regular languages; descriptional complexity

UR - http://eudml.org/doc/245613

ER -

## References

top- [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). Zbl0364.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). Zbl0698.01001
- [4] J.H. Chang, O.H. Ibarra, M.A. Palis and B. Ravikumar, On pebble automata. Theoret. Comput. Sci. 44 (1986) 111–121. Zbl0612.68045
- [5] R. Chang, J. Hartmanis and D. Ranjan, Space bounded computations: Review and new separation results. Theoret. Comput. Sci. 80 (1991) 289–302. Zbl0745.68051
- [6] M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149–158. (Corrigendum: Theoret. Comput. Sci. 302 (2003) 497–498). Zbl0638.68096
- [7] W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985). Zbl0624.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. Zbl0944.68108
- [9] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484–498. Zbl0762.68022
- [10] V. Geffert, Bridging across the $log\left(n\right)$ space frontier. Inform. Comput. 142 (1998) 127–158. Zbl0917.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. Zbl1045.68080
- [12] V. Geffert, C. Mereghetti and G. Pighizzini, Complementing two-way finite automata. Inform. Comput. 205 (2007) 1173–1187. Zbl1121.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. Zbl0874.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. Zbl0229.02033
- [15] J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001). Zbl0980.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. Zbl1039.68068
- [17] Ch.A. Kapoutsis, Deterministic moles cannot solve liveness. J. Automat. Lang. Combin. 12 (2007) 215–235. Zbl1145.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). Zbl0168.25902
- [19] C. Mereghetti and G. Pighizzini, Optimal simulations between unary automata. SIAM J. Comput. 30 (2001) 1976–1992. Zbl0980.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. Zbl0229.94033
- [21] M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114–125. Zbl0158.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. Zbl1282.68160
- [23] A. Salomaa, D. Wood and S. Yu, On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320 (2004) 315–329. Zbl1068.68078
- [24] M. Shepherdson, The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198–200. Zbl0158.25601
- [25] M. Sipser, Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360–364. Zbl0445.68064
- [26] M. Sipser, Halting space bounded computations. Theoret. Comput. Sci. 10 (1980) 335–338. Zbl0423.68011
- [27] A. Szepietowski, Turing Machines with Sublogarithmic Space. Lect. Notes Comput. Sci. 843 (1994). Zbl0998.68062

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.