Quantum finite automata with control language
Mereghetti, Carlo ; Palano, Beatrice
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006), p. 315-332 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1-20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e., to have less states) than the corresponding classical (deterministic) automata.

Publié le : 2006-01-01
DOI : https://doi.org/10.1051/ita:2006007
Classification:  68Q10,  68Q19,  68Q45 
@article{ITA_2006__40_2_315_0,
     author = {Mereghetti, Carlo and Palano, Beatrice},
     title = {Quantum finite automata with control language},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {40},
     year = {2006},
     pages = {315-332},
     doi = {10.1051/ita:2006007},
     mrnumber = {2252642},
     zbl = {1112.68064},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2006__40_2_315_0}
}

Mereghetti, Carlo; Palano, Beatrice. Quantum finite automata with control language. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) pp. 315-332. doi : 10.1051/ita:2006007. http://gdmltest.u-ga.fr/item/ITA_2006__40_2_315_0/

[1] A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M. Mercer and D. Thérien, Algebraic Results on Quantum Automata. Theory Comput. Syst. 39 (2006) 165-188. | Zbl 1101.68029

[2] A. Ambainis and R. Freivalds, 1-way Quantum Finite Automata: Strengths, Weaknesses and Generalizations, in Proc. 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press (1998) 332-342.

[3] A. Ambainis, A. Kikusts and M. Valdats, On the class of languages recognizable by 1-way quantum finite automata, in Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science. Lect. Notes Comput. Sci. 2010 (2001) 305-316. | Zbl 0976.68087

[4] A. Bertoni and M. Carpentieri, Regular languages accepted by quantum automata. Inform. Comput. 165 (2001) 174-182. | Zbl 1003.68061

[5] A. Bertoni, C. Mereghetti and B. Palano, Quantum computing: 1-way quantum automata, in Proc. 7th International Conference on Developments in Language Theory. Lect. Notes Comput. Sci. 2710 (2003) 1-20. | Zbl 1037.68058

[6] A. Bertoni, C. Mereghetti and B. Palano, Golomb Rulers and Difference Sets for Succinct Quantum Automata. Int. J. Found. Comp. Sci. 14 (2003) 871-888. | Zbl 1075.68028

[7] A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theoret. Comput. Sci. 340 (2005) 394-407. | Zbl 1087.68047

[8] A. Bertoni, C. Mereghetti and B. Palano, Some formal tools for analyzing quantum automata. Theoret. Comput. Sci. 356 (2006) 14-25. | Zbl pre05024243

[9] A. Brodsky and N. Pippenger, Characterizations of 1-Way Quantum Finite Automata. SIAM J. Comput. 5 (2002) 1456-1478. | Zbl 1051.68062

[10] M. Golovkins and M. Kravtsev, Probabilistic Reversible Automata and Quantum Automata, in Proc. 8th International Computing and Combinatorics Conference. Lect. Notes Comput. Sci. 2387 (2002) 574-583. | Zbl 1077.68043

[11] J. Gruska, Quantum Computing. McGraw-Hill (1999). | MR 1978991

[12] J. Gruska, Descriptional complexity issues in quantum computing. J. Automata, Languages and Combinatorics 5 (2000) 191-218. | Zbl 0965.68021

[13] J. Hopcroft and J. Ullman, Formal Languages and Their Relation to Automata. Addison-Wesley (1969). | MR 237243 | Zbl 0196.01701

[14] A. Kondacs and J. Watrous, On the Power of Quantum Finite State Automata, in Proc. 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press (1997) 66-75.

[15] C. Moore and J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | Zbl 0939.68037

[16] M. Marcus and H. Minc, Introduction to Linear Algebra. The Macmillan Company (1965). Reprinted by Dover (1988). | MR 1019834 | Zbl 0142.26801

[17] M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities. Prindle, Weber & Schmidt (1964). Reprinted by Dover (1992). | MR 1215484 | Zbl 0126.02404

[18] C. Mereghetti and B. Palano, On the Size of One-way Quantum Finite Automata with periodic behaviors. RAIRO-Inf. Theor. Appl. 36 (2002) 277-291. | Numdam | Zbl 1013.68088

[19] C. Mereghetti, B. Palano and G. Pighizzini, Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO-Inf. Theor. Appl. 35 (2001) 477-490. | Numdam | Zbl 1010.68068

[20] A. Nayak, Optimal lower bounds for quantum automata and random access codes, in Proc. 40th Symposium on Foundations of Computer Science (1999) 369-376. | MR 1917575

[21] J.E. Pin, On Languages Accepted by finite reversible automata, in Proc. 14th Int. Coll. Automata, Languages and Programming. Lect. Notes Comput. Sci. 267 (1987) 237-249. | MR 912712 | Zbl 0627.68069