Abstract.

In the paper we present the solution to the problem of algorithmic synthesis of automata models of Markov’s functions on the basis of aggregation of finite Markov’s chains. Introduced equivalent automata models of Markov’s functions. We determined the dependence of the complexity of algorithmic implementation of automata models from size of a stochastic matrix and length of implication vector of this matrix. Matrix describes law of obtaining of aggregated chain. We estimated the complexity of the considered models.

Keywords:

Markov’s chain, stochastic matrix, autonomic stochastic automata, automata models of Markov’s functions, estimates of the complexity, implicative vector, aggregation of chain.

PP. 32-42. 

REFERENCES

1. Bukharaev R.G. Avtomatnoe preobrazovanie veroyatnostnykh posledovatelnostey // Veroyatnostnye metody i kibernetika. Vyp. 4. Kazan: Izd-vo KGU, 1966. S. 24-33.
2. Bukharaev R.G. Osnovy teorii veroyatnostnykh avtomatov. M.: Nauka, 1985. 287 s.
3. Levin B.R., Shvarts V. Veroyatnostnye modeli i metody v sistemakh svyazi i upravleniya. M.: Radio i svyaz, 1985. 312 s.
4. Davis A.S. Markov chains as random input automata. Amer. Math. Monthly, 1961, 68, 3, pp. 264-267.
5. Chentsov V.M. Ob odnom metode sinteza avtonomnogo stokhasticheskogo avtomata // Kibernetika. Kiev, 1968. №3. S. 32-35.
6. Pospelov D. A. Veroyatnostnye avtomaty. M.: Energiya, 1970. 88 s.
7. Bukharaev R.G., Zakharov V.M., Upravlyaemye generatory sluchaynykh kodov. Kazan: Izd-vo Kazan. un-ta, 1978. 160 s.
8. Gabbasov N.3. Zadacha ob implitsiruyushchem vektore i ee prilozheniyakh // Veroyatnostnye metody i kibernetika. Kazan: Izd-vo KGU, 1987. S. 36-50.
9. Kuznetsov S.Ye., Nurmeev N.N., Salimov F.I. Zadacha o minimalnom implitsiruyushchem vektore // Matematicheskie voprosy kibernetiki. Vyp. №3. Sbornik statey / Pod red. S.V. Yablonskogo. M.: Nauka, Gl. red. fiziko-matematicheskoy literatury, 1991. S. 199-216.
10. Zakharov V.M., Eminov B.F. Analiz algoritmov razlozheniya dvoichno-ratsionalnykh stokhasticheskikh matrits na kombinatsiyu bulevykh matrits // Informatsionnye tekhnologii, №3. M.: Novye tekhnologii, 2008. S. 54-59.
11. Chentsov V.M. Ob odnom metode sinteza avtonomnogo stokhasticheskogo avtomata // Kibernetika. Kiev, Kibernetika, 1968. №3. S. 32-35.
12. Romanovskiy V. Diskretnye tsepi Markova. M.:Gostekhizdat, 1949.436 s.
13. Kemeny J., Snell L. Finite Markov chains. Princeton: Van Nostrand Company. 1960. 210 pp. Kemeni D., Snell D. Konechnye tsepi Markova. M.: Nauka, 1970. 272 s.
14. Korolyuk V.S., Turbin A.F. Polumarkovskie protsessy i ikh prilozheniya. Kiev: Naukova Dumka, 1976. 184 s.
15. Zakharov V.M., Eminov B.F. Algoritmy ukrupneniya tsepey Markova // Vestnik Kazanskogo gosudarstvennogo tekhnicheskogo universiteta im. A.N. Tupoleva, №2 (vypusk 1), 2013. S.125-133.
16. Gambin, A., Pokarowski, P. A new combinatorial algorithm for large Markov chains. Proc. Computer Algebra in Scientific Computing, CASC'01, Springer, Berlin 2001, pp. 195-212. http://bioputer.mimuw.edu.pl/papers/aggr.pdf
17. Ferrari D. Otsenka proizvoditelnosti vychislitelnykh sistem. M.: Mir, 1981. 576s.
18. Franceschinis G., Muntz R. Bounds for quasi-lumpable markov chains. Los Angeles: University of California, 1993. 37 p.
19. Stewart W.J. Introduction to the numerocal solution of Markov chains, Princeton University Press, 1994.
20. Mazurenko I. L. Effektivnyy sposob vvedeniya metriki na mnozhestve nepreryvnykh SMM-avtomatov //Intellektualnye sistemy, tom 11, vypusk 3. M.: Izd-vo MGU, 2007. S. 593-608 (SMM - skrytaya markovskaya model).
21. Deundyak V.M., Zhdanova M.A. Polinomialnoe predstavlenie skrytoy polumarkovskoy modeli fergnesovskogo tipa // Vestnik VGU: sistemnyy analiz i informatsionnye tekhnologii, 2013, №2. S. 71-78.
22. Pogorelov B.A., Pudovkina M.A. Ob obobshcheniyakh markovskogo podkhoda pri izuchenii algoritmov blochnogo shifrovaniya // Prikladnaya diskretnaya matematika. Prilozhenie. Sentyabr 2014. № 7, 2014. S. 51-52.
23. Derisavi, S., Hermanns, H., Sanders, W. H.: Optimal State-Space Lumping in Markov Chains. Information Processing Letters 87 (6), 2003. pp.309–315.
24. Hillston J. Compositional Markovian modelling using a process algebra // Computations with Markov Chains, 1995, pp. 177-196.
25. Geiger B., Temmel C. Lumpings of Markov chains, entropy rate preservation, and highe-order lumpability // Advances in Applied Probability, 51(4), 2014. pp. 1114-1132.
27. Bolch G., Greiner S. Queuing Networks and Markov Chains Modeling and Performance Evaluation with Computer Science Application. Wiley. 2006. 896 p.
28. Katehakis M., Smit L. A Successive Lumping Procedure for a Class of Markov Chains // Probability in the Engineering and Informational Sciences 26 (4), 2012. pp 483-508.
29. Ponomarenko L.A., Melikov A.Z., Nagiev F.N. Analiz sistemy obsluzhivaniya s razlichnymi urovnyami prostranstvennykh i vremennykh prioritetov // Informatsionno-upravlyayushchie kompleksy i sistemy, № 2(18), 2006. S. 80-89.
30. Rozhkov M.I. Summirovanie markovskikh posledovatelnostey na konechnoy abelevoy gruppe//Diskretnaya matematika, №3, t.22, 2010. S.44-62.
31. Maksimov Yu.I. Nekotorye rezultaty dlya zadachi ukrupneniya sostoyaniy tsepey Markova // Trudy po diskretnoy matematike, №8. M.: Fizmatlit, 2004. S. 148-154.
32. Pokhodzey B.B. Slozhnost tablichnykh metodov modelirovaniya konechnykh diskretnykh raspredeleniy // Izv. Vuzov. Matematika. Kazan: Izd-vo KGU, 1985, №7. S. 45-50.
33. Lorents A.A. Sintez nadezhnykh veroyatnostnykh avtomatov. Riga: Zinatne, 1975. 187 s.
34. Eminov B.F., Zakharov V.M. Metody i algoritmy postroeniya i analiza polinomialnykh funktsiy nad konechnym polem na osnove stokhasticheskikh matrits. Saarbrucken: LAP Lambert Academic Publishing, 2011. 161 s.