Abstract
We consider the model of one-way automata with quantum and classical states (qcfas) introduced in [23]. We show, by a direct approach, that qcfas with isolated cut-point accept regular languages only, thus characterizing their computational power. Moreover, we give a size lower bound for qcfas accepting regular languages, and we explicitly build qcfas accepting the word quotients and inverse homomorphic images of languages accepted by given qcfas with isolated cut-point, maintaining the same cut-point, isolation, and polynomially increasing the size.
Partially supported by MIUR under the project “PRIN: Automi e Linguaggi Formali: Aspetti Matematici e Applicativi.”
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M., Thérien, D.: Algebraic results on quantum automata. Theory of Comp. Sys. 39, 165–188 (2006)
Ambainis, A., Watrous, J.: Two-way finite automata with quantum and classical states. Theoretical Computer Science 287, 299–311 (2002)
Bertoni, A., Mereghetti, C., Palano, B.: Quantum computing: 1-way quantum automata. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 1–20. Springer, Heidelberg (2003)
Bertoni, A., Mereghetti, C., Palano, B.: Small size quantum automata recognizing some regular languages. Theoretical Computer Science 340, 394–407 (2005)
Bertoni, A., Mereghetti, C., Palano, B.: Some formal tools for analyzing quantum automata. Theoretical Computer Science 356, 14–25 (2006)
Bertoni, A., Mereghetti, C., Palano, B.: Trace monoids with idempotent generators and measure-only quantum automata. Natural Computing 9, 383–395 (2010)
Bianchi, M.P., Mereghetti, C., Palano, B.: Size Lower Bounds for Quantum Automata. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol. 7956, pp. 19–30. Springer, Heidelberg (2013)
Bianchi, M.P., Palano, B.: Behaviours of unary quantum automata. Fundamenta Informaticae 104, 1–15 (2010)
Brodsky, A., Pippenger, N.: Characterizations of 1-way quantum finite automata. SIAM J. Computing 5, 1456–1478 (2002)
Golovkins, M., Kravtsev, M.: Probabilistic reversible automata and quantum automata. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 574–583. Springer, Heidelberg (2002)
Hirvensalo, M.: Quantum automata with open time evolution. Int. J. Natural Computing Research 1, 70–85 (2010)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (2001)
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proc. 38th Symposium on Foundations of Computer Science (FOCS 1997), pp. 66–75 (1997)
Li, L., Qiu, D., Zou, X., Li, L., Wu, L., Mateus, P.: Characterizations of one-way general quantum finite automata. Theoretical Computer Science 419, 73–91 (2012)
Mercer, M.: Lower bounds for generalized quantum finite automata. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 373–384. Springer, Heidelberg (2008)
Moore, C., Crutchfield, J.: Quantum automata and quantum grammars. Theoretical Computer Science 237, 275–306 (2000)
Mereghetti, C., Palano, B.: Quantum finite automata with control language. Theoretical Informatics and Applications 40, 315–332 (2006)
Mereghetti, C., Palano, B.: Quantum automata for some multiperiodic languages. Theoretical Computer Science 387, 177–186 (2007)
Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: Proc. 40th Symp. Found. Comp. Sci (FOCS 1999), pp. 369–376 (1999)
Salomaa, A., Soittola, M.: Automata theoretic aspects of formal power series. In: Texts and Monographs in Computer Science. Springer (1978)
Schützenberger, M.P.: On the definition of a family of automata. Information and Control 4, 245–270 (1961)
Shilov, G.: Linear Algebra. Prentice Hall (1971); Reprinted by Dover (1977)
Zheng, S., Qiu, D., Li, L., Gruska, J.: One-Way finite automata with quantum and classical states. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Dassow Festschrift 2012. LNCS, vol. 7300, pp. 273–290. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bianchi, M.P., Mereghetti, C., Palano, B. (2014). On the Power of One-Way Automata with Quantum and Classical States. In: Holzer, M., Kutrib, M. (eds) Implementation and Application of Automata. CIAA 2014. Lecture Notes in Computer Science, vol 8587. Springer, Cham. https://doi.org/10.1007/978-3-319-08846-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-08846-4_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08845-7
Online ISBN: 978-3-319-08846-4
eBook Packages: Computer ScienceComputer Science (R0)