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

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

RAIRO - Theoretical Informatics and Applications (2011)

  • 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 (and vice 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 44.4 (2011): 507-523. <http://eudml.org/doc/193073>.

@article{Geffert2011,
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 (and vice 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},
keywords = {Finite automata; regular languages; descriptional complexity; finite automata},
language = {eng},
month = {2},
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/193073},
volume = {44},
year = {2011},
}

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
DA - 2011/2//
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 (and vice 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; finite automata
UR - http://eudml.org/doc/193073
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).  
  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).  
  4. J.H. Chang, O.H. Ibarra, M.A. Palis and B. Ravikumar, On pebble automata. Theoret. Comput. Sci.44 (1986) 111–121.  
  5. R. Chang, J. Hartmanis and D. Ranjan, Space bounded computations: Review and new separation results. Theoret. Comput. Sci.80 (1991) 289–302.  
  6. M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci.47 (1986) 149–158. (Corrigendum: Theoret. Comput. Sci.302 (2003) 497–498).  
  7. W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985).  
  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.  
  9. V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput.20 (1991) 484–498.  
  10. V. Geffert, Bridging across the log ( n ) space frontier. Inform. Comput.142 (1998) 127–158.  
  11. V. Geffert, C. Mereghetti and G. Pighizzini, Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci.295 (2003) 189–203.  
  12. V. Geffert, C. Mereghetti and G. Pighizzini, Complementing two-way finite automata. Inform. Comput.205 (2007) 1173–1187.  
  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.  
  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.  
  15. J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001).  
  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.  
  17. Ch.A. Kapoutsis, Deterministic moles cannot solve liveness. J. Automat. Lang. Combin.12 (2007) 215–235.  
  18. O.B. Lupanov, Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik Akademie-Verlag, Berlin, in German, Vol. 6, 329–335 (1966).  
  19. C. Mereghetti and G. Pighizzini, Optimal simulations between unary automata. SIAM J. Comput.30 (2001) 1976–1992.  
  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.  
  21. M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop.3 (1959) 114–125.  
  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.  
  24. M. Shepherdson, The reduction of two-way automata to one-way automata. IBM J. Res. Develop.3 (1959) 198–200.  
  25. M. Sipser, Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360–364.  
  26. M. Sipser, Halting space bounded computations. Theoret. Comput. Sci.10 (1980) 335–338.  
  27. A. Szepietowski, Turing Machines with Sublogarithmic Space. Lect. Notes Comput. Sci.843 (1994).  

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.