Abstract
Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 4-state unary PFAs recognizing uncountably many languages. After this, we completely characterize the class of languages recognized by 1-state GFAs, which is the only nontrivial class of languages recognized by 1-state automata.
Check arXiv:1405.0055 [SY14] for the full paper.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bertoni, A., Carpentieri, M.: Analogies and differences between quantum and stochastic automata. Theoretical Computer Science 262(1-2), 69–81 (2001)
Hirvensalo, M.: Quantum automata with open time evolution. International Journal of Natural Computing 1(1), 70–85 (2010)
Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoretical Computer Science 237(1-2), 275–306 (2000)
Parikh, R.J.: On context-free languages. Journal of the ACM 13(4), 570–581 (1966)
Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)
Rabin, M.O.: Probabilistic automata. Information and Control 6, 230–243 (1963)
Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and monographs in computer science. Springer, New York (1978)
Shur, A.M., Yakaryılmaz, A.: Quantum, stochastic, and pseudo stochastic languages with few states. Technical Report arXiv:1405.0055 (2014)
Turakainen, P.: Generalized automata and stochastic languages. Proceedings of the American Mathematical Society 21, 303–309 (1969)
Turakainen, P.: Word-functions of stochastic and pseudo stochastic automata. Annales Academiae Scientiarum Fennicae, Series A. I, Mathematica 1, 27–37 (1975)
Yakaryilmaz, A., Say, A.C.C.: Languages recognized with unbounded error by quantum finite automata. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol. 5675, pp. 356–367. Springer, Heidelberg (2009)
Yakaryılmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Information and Computation 10(9&10), 747–770 (2010)
Yakaryılmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Information and Computation 279(6), 873–892 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Shur, A.M., Yakaryılmaz, A. (2014). Quantum, Stochastic, and Pseudo Stochastic Languages with Few States. In: Ibarra, O., Kari, L., Kopecki, S. (eds) Unconventional Computation and Natural Computation. UCNC 2014. Lecture Notes in Computer Science(), vol 8553. Springer, Cham. https://doi.org/10.1007/978-3-319-08123-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-08123-6_27
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08122-9
Online ISBN: 978-3-319-08123-6
eBook Packages: Computer ScienceComputer Science (R0)