Аннотация.

В работе формулируется и доказывается необходимое и достаточное условие реализуемости функций на строках вероятностными автоматами Мура с числовым выходом.

Ключевые слова:

вероятностные автоматы, автоматы Мура, реакции, случайные функции.

Стр. 26-31.

A. M. Mironov

"Towards realizability of string functions by probabilistic automata"

Abstract. In this paper we formulate and prove a necessary and sufficient condition for realizability of string functions by probabilistic Moore automata with numerical output.

Keywords: probabilistic automata, Moore automata, reactions, random functions.

Полная версия статьи в формате pdf. 

REFERENCES 

1. Rabin M. O. Probabilistic automata. Information and Control 6(3), 230–245 (1963). (russkiy perevod: Rabin M. O. Veroyatnostnye avtomaty // Kiberneticheskiy sbornik. Vyp. 9. M.: Inostrannaya literatura, 1964. S. 123–141).
2. Sarlule J. W. Reduced forms for stochastic sequential machines // J. Maht. Analysis and Application. 1963. V. 7. № 2 (russkiy perevod: Karlayl Ye. U. Privedennye formy dlya stokhasticheskikh posledovatelnostnykh mashin // Kiberneticheskiy sbornik. Novaya seriya. M.: Mir, 1966. Vyp. 3. S. 101–110).
3. Bukharaev R. G. Nekotorye ekvivalentnosti v teorii veroyatnostnykh avtomatov // Uch. zapiski Kazan. un-ta. 1964. 124. № 2. S. 45–65.
4. Starke P. H. Theorie stochastischen Automaten, I, II // Elektronische Informationsverarbeitung und Kybernetik. 1965. 1. № 2.
5. Bukharaev R. G. Osnovy teorii veroyatnostnykh avtomatov. M.: Nauka, 1985.
6. Mironov A. M., Frenkel S. L. Minimizatsiya veroyatnostnykh modeley programm // Fundamentalnaya i prikladnaya matematika. T. 19. Vyp. 1. S. 121–163 (2014).
7. Kiefer S., Wachter B. Stability and Complexity of Minimising Probabilistic Automata // J. Esparza et al. (Eds.): ICALP 2014, Part II, LNCS 8573. Springer-Verlag Berlin Heidelberg, 2014. P. 268–279.
8. Mateus P., Qiu D., Li L. On the complexity of minimizing probabilistic and quantum automata // Information and Computation. 218, 36–53 (2012).