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.
Mots-clés : finite automata, regular languages, descriptional complexity
@article{ITA_2010__44_4_507_0, author = {Geffert, Viliam and I\v{s}to\v{n}ov\'a, L'ubom{\'\i}ra}, title = {Translation from classical two-way automata to pebble two-way automata}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {507--523}, publisher = {EDP-Sciences}, volume = {44}, number = {4}, year = {2010}, doi = {10.1051/ita/2011001}, mrnumber = {2775409}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2011001/} }
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 SP - 507 EP - 523 VL - 44 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011001/ DO - 10.1051/ita/2011001 LA - en ID - ITA_2010__44_4_507_0 ER -
%0 Journal Article %A Geffert, Viliam %A Ištoňová, L'ubomíra %T Translation from classical two-way automata to pebble two-way automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2010 %P 507-523 %V 44 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011001/ %R 10.1051/ita/2011001 %G en %F ITA_2010__44_4_507_0
Geffert, Viliam; 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, Tome 44 (2010) no. 4, pp. 507-523. doi : 10.1051/ita/2011001. http://archive.numdam.org/articles/10.1051/ita/2011001/
[1] On the complexity of regular languages in terms of finite automata. Tech. Rep., Vol. 304, Polish Academy of Sciences (1977). | Zbl
and ,[2] Automata on a 2-dimensional tape, in Proc. IEEE Symp. Switching Automata Theory (1967), 155-160.
and ,[3] A History of Mathematics. John Wiley & Sons (1968). | Zbl
,[4] On pebble automata. Theoret. Comput. Sci. 44 (1986) 111-121. | Zbl
, , and ,[5] Space bounded computations: Review and new separation results. Theoret. Comput. Sci. 80 (1991) 289-302. | Zbl
, and ,[6] Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-158. (Corrigendum: Theoret. Comput. Sci. 302 (2003) 497-498). | Zbl
,[7] Prime Numbers. John Wiley & Sons (1985). | Zbl
and ,[8] 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. | Zbl
and ,[9] Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484-498. | Zbl
,[10] Bridging across the space frontier. Inform. Comput. 142 (1998) 127-158. | Zbl
,[11] Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci. 295 (2003) 189-203. | Zbl
, and ,[12] Complementing two-way finite automata. Inform. Comput. 205 (2007) 1173-1187. | Zbl
, and ,[13] Complexity results for two-way and multi-pebble automata and their logics. Theoret. Comput. Sci. 169 (1996) 161-184. | Zbl
and ,[14] Hierarchies of memory limited computations, in IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965), 179-190. | Zbl
, and ,[15] Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001). | Zbl
, and ,[16] 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. | Zbl
and ,[17] Deterministic moles cannot solve liveness. J. Automat. Lang. Combin. 12 (2007) 215-235. | Zbl
,[18] Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik Akademie-Verlag, Berlin, in German, Vol. 6, 329-335 (1966). | Zbl
,[19] Optimal simulations between unary automata. SIAM J. Comput. 30 (2001) 1976-1992. | Zbl
and ,[20] 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. | Zbl
,[21] Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-125. | Zbl
and ,[22] Nondeterminism and the size of two-way finite automata, in Proc. ACM Symp. Theory Comput. (1978), 275-286.
and ,[23] On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320 (2004) 315-329. | Zbl
, and ,[24] The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198-200. | Zbl
,[25] Lower bounds on the size of sweeping automata, in Proc. ACM Symp. Theory Comput. (1979) 360-364. | Zbl
,[26] Halting space bounded computations. Theoret. Comput. Sci. 10 (1980) 335-338. | Zbl
,[27] Turing Machines with Sublogarithmic Space. Lect. Notes Comput. Sci. 843 (1994). | Zbl
,Cité par Sources :