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

详细信息    查看全文

• 作者：Arseny M. Shur ; Abuzer Yakaryılmaz
• 关键词：Stochastic languages ; Unary languages ; Quantum finite automata ; Generalized finite automata ; Probabilistic finite automata ; Regular languages ; Context ; free languages
• 刊名：Natural Computing
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：15
• 期：1
• 页码：129-141
• 全文大小：544 KB
• 参考文献：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–81CrossRef MathSciNet MATH
  Brodsky A, Pippenger N (2002) Characterizations of 1-way quantum finite automata. SIAM J Comput 31(5):1456–1478CrossRef MathSciNet MATH
  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–85CrossRef
  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–306CrossRef MathSciNet MATH
  Parikh RJ (1966) On context-free languages. J ACM 13(4):570–581CrossRef MathSciNet MATH
  Paz A (1971) Introduction to Probabilistic Automata. Academic Press, New YorkMATH
  Rabin MO (1963) Probabilistic automata. Inf Control 6:230–243CrossRef MATH
  Salomaa A, Soittola M (1978) Automata-theoretic aspects of formal power series. Texts and monographs in computer science. Springer, New YorkCrossRef
  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–313CrossRef MathSciNet MATH
  Turakainen P (1969) Generalized automata and stochastic languages. Proc Am Math Soc 21:303–309CrossRef MathSciNet MATH
  Turakainen P (1975) Word-functions of stochastic and pseudo stochastic automata. Ann Acad Sci Fenn 1:27–37CrossRef MathSciNet
  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–770MathSciNet MATH
  Yakaryılmaz A, Say ACC (2011) Unbounded-error quantum computation with small space bounds. Inf Comput 279(6):873–892CrossRef
  Yamakami T, Yao AC (1999) \( {\text{ NQP }}_{\mathbb{C}} = \text{ co-C}_{=}\text{ P }\) . Inf Process Lett 71(2):63–69CrossRef MathSciNet MATH
  
• 作者单位：Arseny M. Shur (1)
  Abuzer Yakaryılmaz (2)
  
  1. Ural Federal University, Ekaterinburg, Russia
  2. National Laboratory for Scientific Computing, Petrópolis, RJ, 25651-075, Brazil
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Evolutionary Biology
  Processor Architectures
  Artificial Intelligence and Robotics
  Complexity
  
• 出版者：Springer Netherlands
• ISSN：1572-9796

文摘

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 3-state unary PFAs recognizing uncountably many languages; all these numbers of states are optimal. 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. Finally, we consider the variations of PFAs, QFAs, and GFAs based on the notion of inclusive/exclusive cutpoint, and present some results on their expressive power.