Quantum finite automata with control language

Carlo Mereghetti; Beatrice Palano

Displaying similar documents to “Quantum finite automata with control language”

On the state complexity of semi-quantum finite automata

Shenggen Zheng, Jozef Gruska, Daowen Qiu (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum finite automata with very little quantumness (so-called semi-quantum one- and two-way finite automata); (b) differences, even comparing...

Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family ${L_{m}}$ of cyclic languages, where $L_{m} = {a^{k m} | k \in ℕ}$ . In particular, we show that, for any $m$ , the number of states necessary and sufficient for accepting the unary language $L_{m}$ with isolated cut point on one-way probabilistic finite automata is $p_{1}^{α_{1}} + p_{2}^{α_{2}} + \dots + p_{s}^{α_{s}}$ , with $p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{s}^{α_{s}}$ being the factorization of $m$ . To prove this result, we give a general state lower bound for accepting unary languages with isolated...

On the size of one-way quantum finite automata with periodic behaviors

Carlo Mereghetti, Beatrice Palano (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We show that, for any stochastic event $p$ of period $n$ , there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2 \sqrt{6 n} + 25$ states inducing the event $a p + b$ , for constants $a > 0$ , $b \geq 0$ , satisfying $a + b \leq 1$ . This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period $n$ can be accepted with isolated cut point by a 1qfa with no more than $2 \sqrt{6 n} + 26$ states. Our results give added evidence of the strength...

Translation from classical two-way automata to pebble two-way automata

Viliam Geffert, L'ubomíra Ištoňová (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

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....

Discourse on one way in which a quantum-mechanics language on the classical logical base can be built up

Roman Bek (1978)

Kybernetika

Similarity:

Superiority of one-way and realtime quantum machines

Abuzer Yakaryılmaz (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

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...

Hyper-minimizing minimized deterministic finite state automata

Andrew Badr, Viliam Geffert, Ian Shipman (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications,...