|
А. М. Миронов "О реализуемости функций на строках вероятностными автоматами" |
|
Аннотация. В работе формулируется и доказывается необходимое и достаточное условие реализуемости функций на строках вероятностными автоматами Мура с числовым выходом. Ключевые слова: вероятностные автоматы, автоматы Мура, реакции, случайные функции. Стр. 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).
|