On Almost-Sure Properties of Probabilistic Discrete Event Systems

• Autorzy: Yen H-C.
• Języki publikacji: EN

Abstrakty

EN

Although randomization often increases the degree of flexibility in system design, analyzing system properties in the probabilistic framework introduces additional difficulties and challenges in comparison with their nonprobabilistic counterparts. In this paper, we focus on probabilistic versions of two problems frequently encountered in discrete event systems, namely, the reachability and forbidden-state problems. Our main concern is to see whether there exists a (or for every) non-blocking or fair control policy under which a given finite- or infinite-state system can be guided to reach (or avoid) a set of goal states with probability one. For finite-state systems, we devise algorithmic approaches which result in polynomial time solutions to the two problems. For infinite-state systems modelled as Petri nets, the problems are undecidable in general. For the class of persistent Petri nets, we establish a valuation approach through which the convergence behavior of a system is characterized, which in turn yields solutions to the reachability and forbidden-state problems.

Słowa kluczowe

EN

forbidden-state avoidance; Petri net; probabilistic controlled transition system; reachability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 343--359
• Opis fizyczny: Bibliogr. 11 poz., wykr.

Twórcy

autor

Yen H-C.

• Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan 106, R.O.C.,

Bibliografia

• [1] Abdulla, P., Henda, N., Mayr, R.: Verifying infinite Markov chains with a finite attractor or the global coarseness property, in Proc. 20th Annual IEEE Symposium on Logic in Computer Science, 127-136, 2005.
• [2] Baier, C., Gröer, M., Leucker, M., Bollig, B., Ciesinski. F.: Controller synthesis for probabilistic systems, in Proc. IFIP International Conference on Theoretical Computer Science, J.-J. Lévy, E. W. Mayr, and J. C. Mitchell, Eds. Kluwer, 493-506, 2004.
• [3] Brázdil, T., Forejt, V., Kučera, A.: Controller synthesis and verification for Markov decision processes with qualitative branching time objectives, in Proc. 35th International Colloquium on Automata, Languages and Programming, 148-159, 2008.
• [4] Garg, V.: Probabilistic languages for modeling of DEDS. in Proc. 26th Conference on Information Sciences and Systems, Vol. 1, 198-203, 1992.
• [5] Kučera, A., Strazovsky, O.: On the controller synthesis for finite-state Markov decision processes, Fundamenta Informaticae, Vol. 82, No. 1-2, 141-153, 2008.
• [6] Landweber, L., Robertson, E.: Properties of conflict-free and persistent Petri nets, JACM 25(3): 352-364, 1978.
• [7] Lawford, M., Wonham, W.: Supervisory control of probabilistic discrete event systems, in Proc. 36th IEEE Midwest Symposium on Circuits and Systems, Vol. 1. IEEE, 327-331, 1993.
• [8] Pantelic, V., Postma, S., Lawford, M.: Probabilistic supervisory control of probabilistic discrete event systems, IEEE Transactions on Automatic Control, Vol. 54, No. 8, 2013-2018, 2009.
• [9] Rosier, L., Yen, H.: On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, Theoretical Computer Science, Vol. 58, No. 1-3, 263-324, 1988.
• [10] Yen, H.: A valuation-based analysis of conflict-free Petri nets, Systems and Control Letters, Vol. 45, No. 5, 387-395, 2002.
• [11] Yen, H.: Decidability and complexity analysis of forbidden state problems for discrete event systems, International Journal of Foundations of Computer Science, Vol. 19, No. 4, 999-1013, 20