Voir la notice de l'article provenant de la source Numdam
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.
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :