More on quantum, stochastic, and pseudo stochastic languages with few states

• Ambainis A, Freivalds R (1998) 1-way quantum finite automata: strengths, weaknesses and generalizations. In: FOCS’98: Proceedings of the 39th annual symposium on foundations of computer science, pp 332–341. (http://arxiv.org/abs/quant-ph/9802062)

• Bertoni A, Carpentieri M (2001) Analogies and differences between quantum and stochastic automata. Theor Comput Sci 262(1–2):69–81

  Article  MathSciNet  MATH  Google Scholar 

• Brodsky A, Pippenger N (2002) Characterizations of 1-way quantum finite automata. SIAM J Comput 31(5):1456–1478

  Article  MathSciNet  MATH  Google Scholar 

• Bukharaev RG (1967) Probabilistic methods and cybernetics. V, Gos. Univ. Uchen. Zap., vol 127:3, chap. On the representability of events in probabilistic automata, pp 7–20. Kazan (Russian)

• Hirvensalo M (2010) Quantum automata with open time evolution. Int J Nat Comput 1(1):70–85

  Article  Google Scholar 

• Macarie I (1993) Closure properties of stochastic languages. Technical report 441, University of Rochester

• Moore C, Crutchfield JP (2000) Quantum automata and quantum grammars. Theor Comput Sci 237(1–2):275–306

  Article  MathSciNet  MATH  Google Scholar 

• Parikh RJ (1966) On context-free languages. J ACM 13(4):570–581

  Article  MathSciNet  MATH  Google Scholar 

• Paz A (1971) Introduction to Probabilistic Automata. Academic Press, New York

  MATH  Google Scholar 

• Rabin MO (1963) Probabilistic automata. Inf Control 6:230–243

  Article  MATH  Google Scholar 

• Salomaa A, Soittola M (1978) Automata-theoretic aspects of formal power series. Texts and monographs in computer science. Springer, New York

  Book  Google Scholar 

• Say ACC, Yakaryılmaz A (2015) Quantum finite automata: a modern introduction. In: Gruska Festschrift, LNCS, vol 8808. Springer, pp 208–222

• Shur AM, Yakaryilmaz A (2014) Quantum, stochastic, and pseudo stochastic languages with few states. In: Unconventional computation and natural computation, LNCS, vol 8553. Springer, Switzerland, pp 327–339

• Turakainen P (1968) On stochastic languages. Inf Control 12(4):304–313

  Article  MathSciNet  MATH  Google Scholar 

• Turakainen P (1969) Generalized automata and stochastic languages. Proc Am Math Soc 21:303–309

  Article  MathSciNet  MATH  Google Scholar 

• Turakainen P (1975) Word-functions of stochastic and pseudo stochastic automata. Ann Acad Sci Fenn 1:27–37

  Article  MathSciNet  Google Scholar 

• Yakaryılmaz A, Say ACC (2009) Languages recognized with unbounded error by quantum finite automata. In: CSR’09: Proceedings of the fourth international computer science symposium in Russia, LNCS, vol 5675, pp 356–367

• Yakaryılmaz A, Say ACC (2010) Languages recognized by nondeterministic quantum finite automata. Quantum Inf Comput 10(9, 10):747–770

  MathSciNet  MATH  Google Scholar 

• Yakaryılmaz A, Say ACC (2011) Unbounded-error quantum computation with small space bounds. Inf Comput 279(6):873–892

  Article  Google Scholar 

• Yamakami T, Yao AC (1999) \( {\text{ NQP }}_{\mathbb{C}} = \text{ co-C}_{=}\text{ P }\). Inf Process Lett 71(2):63–69

  Article  MathSciNet  MATH  Google Scholar 

Download references