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

Mereghetti, Carlo; Palano, Beatrice

doi:10.1051/ita:2002014

Geodesic

Parcourir par

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

Mereghetti, Carlo ; Palano, Beatrice

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 277-291

Voir la notice de l'article provenant de la source Numdam

Résumé

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 of measure-once 1qfa’s with respect to classical automata.

EuDML MR Zbl

DOI : 10.1051/ita:2002014

Classification : 68Q10, 68Q19, 68Q45
Keywords: quantum finite automata, periodic events and languages

@article{ITA_2002__36_3_277_0,
     author = {Mereghetti, Carlo and Palano, Beatrice},
     title = {On the size of one-way quantum finite automata with periodic behaviors},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {277--291},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {3},
     year = {2002},
     doi = {10.1051/ita:2002014},
     mrnumber = {1958244},
     zbl = {1013.68088},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2002014/}
}

TY  - JOUR
AU  - Mereghetti, Carlo
AU  - Palano, Beatrice
TI  - On the size of one-way quantum finite automata with periodic behaviors
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2002
SP  - 277
EP  - 291
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2002014/
DO  - 10.1051/ita:2002014
LA  - en
ID  - ITA_2002__36_3_277_0
ER  -

%0 Journal Article
%A Mereghetti, Carlo
%A Palano, Beatrice
%T On the size of one-way quantum finite automata with periodic behaviors
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 277-291
%V 36
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2002014/
%R 10.1051/ita:2002014
%G en
%F ITA_2002__36_3_277_0

Mereghetti, Carlo; Palano, Beatrice. On the size of one-way quantum finite automata with periodic behaviors. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 277-291. doi: 10.1051/ita:2002014

Cité par Sources :