RAIRO-Theor. Inf. Appl.
Volume 46, Number 4, October-December 2012Special Issue: Non-Classical Models of Automata and Applications III (NCMA-2011)
|Page(s)||615 - 641|
|Published online||08 October 2012|
Superiority of one-way and realtime quantum machines∗,∗∗
University of Latvia, Faculty of Computing,
Raina bulv. 19, LV-1586
Accepted: 8 June 2012
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.
Mathematics Subject Classification: 68Q05 / 68Q10 / 68Q12 / 68Q45
Key words: Quantum computation / quantum automata / blind counter automata / multihead finite automata / nondeterminism / bounded error
© EDP Sciences 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.