Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102293
Title: Quantum, stochastic, and pseudo stochastic languages with few states
Authors: Shur, A. M.
YakaryIlmaz, A.
Issue Date: 2014
Publisher: Springer Verlag
Citation: Shur A. M. Quantum, stochastic, and pseudo stochastic languages with few states / A. M. Shur, A. YakaryIlmaz. — DOI 10.1007/978-3-319-08123-6_27 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8553 LNCS. — P. 327-339.
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. © 2014 Springer International Publishing Switzerland.
Keywords: GENERALIZED FINITE AUTOMATA
PROBABILISTIC FINITE AUTOMATA
QUANTUM FINITE AUTOMATA
STOCHASTIC LANGUAGES
UNARY LANGUAGES
FINITE AUTOMATA
QUANTUM THEORY
BINARY ALPHABETS
COMPUTATIONAL MODEL
CUT-POINT
GENERALIZED FINITE AUTOMATON
PROBABILISTIC FINITE AUTOMATA
QUANTUM FINITE AUTOMATA
REAL NUMBER
UNARY LANGUAGES
STOCHASTIC SYSTEMS
URI: http://hdl.handle.net/10995/102293
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84958545509
PURE ID: 368290
8bc9b7db-9d48-40af-8f2a-ee91831017a7
ISSN: 3029743
ISBN: 9783319081229
DOI: 10.1007/978-3-319-08123-6_27
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84958545509.pdf283,49 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.