More on quantum, stochastic, and pseudo stochastic languages with few states / Shur Arseny M.,Yakaryilmaz Abuzer // NATURAL COMPUTING. - 2016. - V. 15, l. 1, SI. - P. 129-141.

ISSN/EISSN:

1567-7818 / 1572-9796

Type:

Article

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.

Author keywords:

Stochastic languages; Unary languages; Quantum finite automata; Generalized finite automata; Probabilistic finite automata; Regular languages; Context-free languages FINITE AUTOMATA

DOI:

10.1007/s11047-015-9511-8

Web of Science ID:

ISI:000371310400011

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	MAR
Publisher	SPRINGER
Address	VAN GODEWIJCKSTRAAT 30, 3311 GZ DORDRECHT, NETHERLANDS
Language	English
EISSN	1572-9796
Keywords-Plus	FINITE AUTOMATA
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Artificial Intelligence; Computer Science, Interdisciplinary Applications; Computer Science, Theory \& Methods
Author-Email	arseny.shur@urfu.ru abuzer@lncc.br
ORCID-Numbers	YAKARYILMAZ, ABUZER/0000-0002-2372-252X
Funding-Acknowledgement	Ministry of Education and Science of the Russian Federation {[}02.A03.21.0006]; Ural Federal University {[}02.A03.21.0006]; CAPES {[}88881.030338/2013-01]; ERC Advanced Grant MQC; FP7 FET Projects QALGO
Funding-Text	Arseny M. Shur was partially supported under the Agreement 02.A03.21.0006 of 27.08.2013 between the Ministry of Education and Science of the Russian Federation and Ural Federal University. Abuzer Yakaryilmaz was partially supported by CAPES with Grant 88881.030338/2013-01, ERC Advanced Grant MQC, and FP7 FET Projects QALGO.
Number-of-Cited-References	19
Journal-ISO	Nat. Comput.
Doc-Delivery-Number	DF4IE