# 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

## 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 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- 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
- 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).
- J.H. Chang, O.H. Ibarra, M.A. Palis and B. Ravikumar, On pebble automata. Theoret. Comput. Sci.44 (1986) 111–121.
- R. Chang, J. Hartmanis and D. Ranjan, Space bounded computations: Review and new separation results. Theoret. Comput. Sci.80 (1991) 289–302. Zbl0745.68051
- M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci.47 (1986) 149–158. (Corrigendum: Theoret. Comput. Sci.302 (2003) 497–498). Zbl0638.68096
- 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.
- V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput.20 (1991) 484–498. Zbl0762.68022
- V. Geffert, Bridging across the $log\left(n\right)$ space frontier. Inform. Comput.142 (1998) 127–158. Zbl0917.68077
- 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
- V. Geffert, C. Mereghetti and G. Pighizzini, Complementing two-way finite automata. Inform. Comput.205 (2007) 1173–1187. Zbl1121.68063
- 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
- 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). Zbl0980.68066
- 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
- Ch.A. Kapoutsis, Deterministic moles cannot solve liveness. J. Automat. Lang. Combin.12 (2007) 215–235. Zbl1145.68461
- 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
- C. Mereghetti and G. Pighizzini, Optimal simulations between unary automata. SIAM J. Comput.30 (2001) 1976–1992. Zbl0980.68048
- 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
- M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop.3 (1959) 114–125. Zbl0158.25404
- 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
- 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
- M. Shepherdson, The reduction of two-way automata to one-way automata. IBM J. Res. Develop.3 (1959) 198–200. Zbl0158.25601
- M. Sipser, Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360–364.
- M. Sipser, Halting space bounded computations. Theoret. Comput. Sci.10 (1980) 335–338. Zbl0423.68011
- 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.