Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-23T06:20:50.616Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  28 February 2011

Viliam Geffert  and
L'ubomíra Ištoňová
Viliam Geffert
Affiliation:
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 040 01 Košice, Slovakia; [email protected]; [email protected]
L'ubomíra Ištoňová
Affiliation:
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 040 01 Košice, Slovakia; [email protected]; [email protected]
Get access

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.

Keywords

Finite automataregular languagesdescriptional complexity
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 4 , October 2010 , pp. 507 - 523
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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).
M. Blum and C. Hewitt, Automata on a 2-dimensional tape, in Proc. IEEE Symp. Switching Automata Theory (1967), 155–160.
C. Boyer, A History of Mathematics. John Wiley & Sons (1968).
Chang, J.H., Ibarra, O.H., Palis, M.A. and Ravikumar, B., On pebble automata. Theoret. Comput. Sci. 44 (1986) 111–121. CrossRef
Chang, R., Hartmanis, J. and Ranjan, D., Space bounded computations: Review and new separation results. Theoret. Comput. Sci. 80 (1991) 289–302.
Chrobak, M., Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149–158. (Corrigendum: Theoret. Comput. Sci. 302 (2003) 497–498). CrossRef
W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985).
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.
Geffert, V., Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484–498. CrossRef
Geffert, V., Bridging across the $\log(n)$ space frontier. Inform. Comput. 142 (1998) 127–158. CrossRef
Geffert, V., Mereghetti, C. and Pighizzini, G., Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci. 295 (2003) 189–203. CrossRef
Geffert, V., Mereghetti, C. and Pighizzini, G., Complementing two-way finite automata. Inform. Comput. 205 (2007) 1173–1187. CrossRef
Globerman, N. and Harel, D., Complexity results for two-way and multi-pebble automata and their logics. Theoret. Comput. Sci. 169 (1996) 161–184. CrossRef
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.
J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001).
Hromkovič, J. and Schnitger, G., 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. CrossRef
Kapoutsis, Ch.A., Deterministic moles cannot solve liveness. J. Automat. Lang. Combin. 12 (2007) 215–235.
O.B. Lupanov, Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik Akademie-Verlag, Berlin, in German, Vol. 6, 329–335 (1966).
Mereghetti, C. and Pighizzini, G., Optimal simulations between unary automata. SIAM J. Comput. 30 (2001) 1976–1992. CrossRef
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. CrossRef
Rabin, M. and Scott, D., Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114–125. CrossRef
W. Sakoda and M. Sipser, Nondeterminism and the size of two-way finite automata, in Proc. ACM Symp. Theory Comput. (1978), 275–286.
Salomaa, A., Wood, D. and On, S. Yu the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320 (2004) 315–329. CrossRef
Shepherdson, M., The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198–200. CrossRef
M. Sipser, Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360–364.
Sipser, M., Halting space bounded computations. Theoret. Comput. Sci. 10 (1980) 335–338. CrossRef
A. Szepietowski, Turing Machines with Sublogarithmic Space. Lect. Notes Comput. Sci. 843 (1994).