Voir la notice de l'article provenant de la source Numdam
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.
@article{ITA_2012__46_4_615_0,
author = {Yakary{\i}lmaz, Abuzer},
title = {Superiority of one-way and realtime quantum machines},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {615--641},
publisher = {EDP-Sciences},
volume = {46},
number = {4},
year = {2012},
doi = {10.1051/ita/2012018},
mrnumber = {3107866},
zbl = {1279.68090},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2012018/}
}
TY - JOUR AU - Yakaryılmaz, Abuzer TI - Superiority of one-way and realtime quantum machines JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 615 EP - 641 VL - 46 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2012018/ DO - 10.1051/ita/2012018 LA - en ID - ITA_2012__46_4_615_0 ER -
%0 Journal Article %A Yakaryılmaz, Abuzer %T Superiority of one-way and realtime quantum machines %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 615-641 %V 46 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2012018/ %R 10.1051/ita/2012018 %G en %F ITA_2012__46_4_615_0
Yakaryılmaz, Abuzer. Superiority of one-way and realtime quantum machines. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 4, pp. 615-641. doi: 10.1051/ita/2012018
Cité par Sources :