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

Abstract

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

How to cite

top

Geffert, 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. [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. [2] M. Blum and C. Hewitt, Automata on a 2-dimensional tape, in Proc. IEEE Symp. Switching Automata Theory (1967), 155–160. 
  3. [3] C. Boyer, A History of Mathematics. John Wiley & Sons (1968). Zbl0698.01001
  4. [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. [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. [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. [7] W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985). Zbl0624.10001
  8. [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. [9] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484–498. Zbl0762.68022
  10. [10] V. Geffert, Bridging across the log ( n ) space frontier. Inform. Comput. 142 (1998) 127–158. Zbl0917.68077
  11. [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. [12] V. Geffert, C. Mereghetti and G. Pighizzini, Complementing two-way finite automata. Inform. Comput. 205 (2007) 1173–1187. Zbl1121.68063
  13. [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. [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. [15] J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001). Zbl0980.68066
  16. [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. [17] Ch.A. Kapoutsis, Deterministic moles cannot solve liveness. J. Automat. Lang. Combin. 12 (2007) 215–235. Zbl1145.68461
  18. [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. [19] C. Mereghetti and G. Pighizzini, Optimal simulations between unary automata. SIAM J. Comput. 30 (2001) 1976–1992. Zbl0980.68048
  20. [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. [21] M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114–125. Zbl0158.25404
  22. [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. [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. [24] M. Shepherdson, The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198–200. Zbl0158.25601
  25. [25] M. Sipser, Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360–364. Zbl0445.68064
  26. [26] M. Sipser, Halting space bounded computations. Theoret. Comput. Sci. 10 (1980) 335–338. Zbl0423.68011
  27. [27] A. Szepietowski, Turing Machines with Sublogarithmic Space. Lect. Notes Comput. Sci. 843 (1994). Zbl0998.68062

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.