Informatics and Applications

2015, Volume 9, Issue 3, pp 85-96

REALIZABILITY OF PROBABILISTIC REACTIONS BY FINITE PROBABILISTIC AUTOMATA

A. M. Mironov

Abstract

The paper considers the problem of optimizing the access control on a set of dynamic threshold strategies in an M/D/1 system. If the number of concurrent requests in a system is more than the threshold then the system stops accepting requests. If the number of requests is less or equal to this value, then the system resumes accepting requests. As a target function, the average value of the marginal revenue obtained per time unit in the stationary mode is used. It is assumed that the system receives a fixed fee for each accepted request and pays a fixed penalty for each overdue service of a request. The system does not receive a fee and does not pay a penalty for each rejected request. Estimates of the optimal value of the target function and the optimal threshold value are obtained.

[+] References (28)

Rabin, M.O. 1963. Probabilistic automata. Information Control 6(3):230-245.
Hopcroft, J. E., R. Motwani, and J. D. Ullman. 2006. Introduction to automata theory, languages, and computation 3rd ed. Pearson. 750 p.
Kemeny, J. G., and J. L. Snell. 1976. Finite Markov chains. New York - Berlin - Heidelberg - Tokyo: Springer-Verlag. 225 p.
Carlyle, J. W. 1963. Reduced forms for stochastic sequential machines. J. Math. Anal. Appl. 7(2):167-175.
Bukharaev, R. G. 1964. Nekotorye ekvivalentnosti v teorii veroyatnostnykh avtomatov [Certain equivalences in the theory of probabilistic automata]. Uchenye zapiski Kazanckogo Universiteta [Lecture Notes of Kazan Univer-sity] 124(2):45-65.
Starke, P H. 1965. Theorie stochastischen Automaten. Elektronische Informationsverarbeitung und Kybernetik 1(2):5-32.
Paz, A. 1971. Introduction to probabilistic automata. New York, NY: Academic Press. 228 p.
Bukharaev, R. G. 1985. Osnovy teorii veroyatnostnykh avtomatov [Foundations of probabilistic automata theory]. Moscow: Nauka. 288 p.
Segala, R., and N.A. Lynch. 1995. Probabilistic simulations for probabilistic processes. Nordic J. Computing 2(2):250-273.
Stoelinga, M. 2002. An introduction to probabilistic automata. Bull. Eur. Assoc. Theor. Comput. Sci. 78:176- 198.
Sokolova, A., and E. P de Vink. 2004. Probabilistic automata: System types, parallel composition and comparison. Validation of stochastic systems - a guide to current research. Eds. Ch. Baier, B. R. Haverkort, H. Hermanns, J.-P Katoen, and M. Siegle. Lecture notes in computer science ser. Springer. 2925:1-43.
Rabiner, L. R. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77(2):257-286.
Darwiche, A. 2009. Modeling and reasoning with Bayesian networks. Cambridge University Press. 562 p.
Koller, D., and N. Friedman. 2009. Probabilistic graphical models. Principles and techniques. Massachusetts: MIT Press. 1280 p.
Feinberg, E.A., and A. Shwartz, eds. 2002. Handbook of Markov decision processes. Boston, MA: Kluwer. 562 p.
Wu, S.-H., S. A. Smolka, andE.W Stark. 1997. Composition and behaviors ofprobabilistic I/O automata. Theor. Comput. Sci. 176(1)1-38.
Delahaye, B., J.-P Katoen, K. G. Larsen, A. Legay, M. L. Pedersen, F. Sher, and A. Wasowski. 2013. Abstract probabilistic automata. Inform. Comput. 232:66-116.
Kudlek, M. 2005. Probability in Petri nets. Fund. Inform. 67(1):121-130.
Liu, Y., H. Miao, H. Zeng, and Z. Li. 2011. Probabilistic Petri net and its logical semantics. 9th Conference (Inter-national) on Software Engineering Research, Management and Applications Proceedings. 73-78.
Eisentraut, C., H. Hermanns, and L. Zhang. 2010. On probabilistic automata in continuous time. 25th Annual IEEE Symposium on Logic in Computer Science (LICS) Proceedings. 342-351.
Jonsson, B., K. G. Larsen, and W Yi. 2001. Probabilistic extensions of process algebras. Handbook of process algebra. North Holland: Elsevier. 685-710.
Homuth, H. H. 1971. A type of stochastic automation applicable to the communication channel. Angewandte Informatik 8:362-372.
Bukharaev, R. G. 1975. Teoriya abstraktnykh veroyat-nostnykh avtomatov [A theory of abstract probabilistic automata]. Problemy Kibernetiki [Problems Cybernetics] 30:147-198.
Moore, E. F 1956. Gedanken-experiments on sequential machines. Automata Studies. Annals of Mathematical Studies. Princeton University Press. 34:129-153.
Bukharaev, R. G. 2007. Seti veroyatnostnykh protsessorov [Networks of probabilistic processors]. Matematicheskie Voprosy Kibernetiki [Mathematical Issues of Cybernetics] 16:57-72.
Mateus, P., D. Qiu, and L. Li. 2012. On the complexity of minimizing probabilistic and quantum automata. Inform. Comput. 218:36-53.
Mironov, A.M., and S. L. Frenkel. 2014. Minimiza- tsiya veroyatnostnykh modeley programm [Minimization of probabilistic models of programs]. Fundamental'naya i Prikladnaya Matematika [Fundamental Applied Mathe-matics] 19(1):121-163.
Kiefer, S., and B. Wachter. 2014. Stability and complexity of minimising probabilistic automata. Automata, languages, and programming. Eds. J. Esparza, P. Fraigni- aud, Th. Husfeldt, and E. Koutsoupias. Lecture notes in computer science ser. Springer. 8573:268-279.

[+] About this article