Paper Info
Title
More on quantum, stochastic, and pseudo stochastic languages with few states
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 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.
Year
DOI
Venue
2014
10.1007/s11047-015-9511-8
Natural Computing
Keywords
Field
DocType
Stochastic languages,Unary languages,Quantum finite automata,Generalized finite automata,Probabilistic finite automata,Regular languages,Context-free languages
Quantum finite automata,Discrete mathematics,Context-free language,Unary operation,Nested word,Abstract family of languages,Cone (formal languages),Regular language,Probabilistic automaton,Mathematics
Conference
Volume
Issue
ISSN
15
1
1567-7818
Citations 
PageRank 
References 
5
0.51
10
Authors
2
Name
Order
Citations
PageRank
Arseny M. Shur115226.47
Abuzer Yakaryilmaz216825.31