Algebraic structure of some stochastic discrete event systems, with applications. (English) Zbl 0738.93068

Summary: Generalized semi-Markov processes (GSMPs) and stochastic Petri nets (SPNs) are generally regarded as performance models (as opposed to logical models) of discrete event systems. Here we take the view that GSMPs and SPNs are essentially automata (generators) driven by input sequences that determine the timing of events. This view combines the deterministic, logical aspects and the stochastic, timed aspects of the two models. We focus on two conditions, (M) and (CX) (which we previously developed to study montonicity and convexity properties of GSMPs), and the antimatroid and lattice structure they imply for the langauge generated by a GSMP of SPN. We illustrate applications of these structural properties in the areas of derivative estimation, simulation variance reduction, parallel simulation, and optimal control.


93E03 Stochastic systems in control theory (general)
93B25 Algebraic methods
60J99 Markov processes
Full Text: DOI


[1] F. Baccelli, ”Ergodic theory of stochastic decision free Petri nets,” inProc. 28th IEEE Conf. Decision and Control, 1989, pp. 1521–1527. (Extended version to appear inAnn. Probab.)
[2] F. Baccelli and A. M. Makowski, ”Queueing models for systems with synchronization constraints,”Proc. IEEE, Vol. 77, pp. 138–161, 1989. · doi:10.1109/5.21076
[3] A. Björner ”On matroids, groups, and exchange languages,” inMatroid Theory and Its Applications (eds. L. Lovász and A. Rechksi), Colloq. Math. Soc. J. Bolyai 40, North-Holland: Amsterdam, 1985; pp. 25–60. · Zbl 0642.05012
[4] P. Bratley, B. L. Fox, and L. E. Schrage,A Guide to Simulation, Springer-Verlag: New York, 1983. · Zbl 0515.68070
[5] C. G. Cassandras and S. G. Strickland, ”Sample path properties of timed discrete event systems,”Proc. IEEE, Vol. 77, pp. 59–71, 1989. · doi:10.1109/5.21070
[6] K. M. Chong, ”Some extensions of a theorem of Hardy, Littlewood and Polya and their applications,”Canad. J. Math., Vol. 26, pp. 1321–1340, 1974. · Zbl 0295.28006 · doi:10.4153/CJM-1974-126-1
[7] G. Cohen, P. Moller, J.-P., Quadrat, and M. Viot, ”Algebraic tools for the performance analysis of discrete event systems,Proc. IEEE, Vol. 77, pp. 39–58, 1989. · doi:10.1109/5.21069
[8] S. Crespi-Reghizzi, ”Petri nets and Szilard languages,”Inform. Control, Vol. 33, pp. 177–192, 1977. · Zbl 0354.68098 · doi:10.1016/S0019-9958(77)90558-7
[9] S. Crespi-Reghizzi and D. Mandrioli, ”A decidability theorem for a class of vector-addition systems,”Inform. Process. Lett., Vol. 3, pp. 78–80, 1975. · Zbl 0302.68065 · doi:10.1016/0020-0190(75)90020-4
[10] B. L. Dietrich, ”Matroids and antimatroids–a survey,”Discrete Math., Vol. 78, pp. 223–237, 1989. · Zbl 0723.05025 · doi:10.1016/0012-365X(89)90180-5
[11] P. Glasserman, ”Structural conditions for perturbation analysis derivative estimation: Finite-time performance indices, 1989,Operations Research, Forthcoming. · Zbl 0743.60086
[12] P. Glasserman and D. D. Yao, ”Monotonicity in generalized semi-Markov processes,” 1989,Math. of Oper. Res., forthcoming. · Zbl 0753.60082
[13] P. Glasserman and D. D. Yao, ”Generalized semi-Markov processes: Antimatroid structure and second-order properties, 1990,Math. Oper. Res., forthcoming. · Zbl 0753.60086
[14] P. W. Glynn, ”A GSMP formalism for discrete event systems,”Proc. IEEE, Vol. 77, pp. 14–23, 1989. · doi:10.1109/5.21067
[15] A. G. Greenberg, G. D. Lubachevsky, and I. Mitrani, ”Unboundedly parallel simulations via recurrence relations,”Sigmetrics ’90, Boulder, CO, 1990.ACM Trans. Comput. Syst., forthcoming.
[16] P. J. Haas and G. S. Schedler, ”Modeling power of stochastic Petri nets,”Probab. Eng. Inform. Sci., Vol. 2, pp. 435–459, 1988. · Zbl 1134.68442 · doi:10.1017/S0269964800000152
[17] Y. C. Ho, ”Performance evaluation and perturbation analysis of discrete event dynamic systems: Perspectives and open problems,”IEEE Trans. Automat. Control, Vol. AC-32, pp. 563–572, 1987. · Zbl 0627.93034 · doi:10.1109/TAC.1987.1104665
[18] J. Q. Hu, ”Convexity of sample path performances and strong consistency of infinitesimal perturbation analysis estimates,”IEEE Trans. Automat. Control, July, 1991, forthcoming.
[19] M. R. Karp and R. E. Miller, ”Parallel program schemata,”J. Comput. Syst. Sci., Vol. 3, pp. 147–195; 1969. · Zbl 0198.32603 · doi:10.1016/S0022-0000(69)80011-5
[20] R. E. Ladner and M. J. Fischer, ”Parallel prefix computation,”J. ACM, Vol. 27, pp. 831–838, 1980. · Zbl 0445.68066 · doi:10.1145/322217.322232
[21] F. Lin and D. D. Yao, ”Generalized semi-Markov processes: A view through supervisory control,Proc. 28th IEEE Conf. Decision and Control, 1989, pp. 1075–1076.
[22] G. G. Lorentz, ”An inequality for rearrangements,”Amer. Math. Monthly, Vol. 60, pp. 176–179, 1953. · Zbl 0050.28201 · doi:10.2307/2307574
[23] R. Parikh, ”On context-free languages,”J. ACM, Vol. 13, pp. 570–581, 1966. · Zbl 0154.25801 · doi:10.1145/321356.321364
[24] J. L. Peterson, ”Computation sequence sets,”J. Comput. Syst. Sci., Vol. 13, pp. 1–24, 1976. · Zbl 0354.68100 · doi:10.1016/S0022-0000(76)80047-5
[25] J. L. Peterson,Petri Net Theory and the Modeling of Systems, Prentice-Hall: Englewood Cliffs, NJ, 1981. · Zbl 0461.68059
[26] P. J. Ramadge and W. M. Wonham, ”Supervisory control of a class of discrete-event processes,”SIAM J. Control Optim., Vol. 25, pp. 206–230, 1987. · Zbl 0618.93033 · doi:10.1137/0325013
[27] C. V. Ramamoorthy and G. S. Ho, ”Performance evaluation of asynchronous concurrent systems using Petri nets,”IEEE Trans. Software Eng., Vol. SE-6, pp. 440–449, 1980. · doi:10.1109/TSE.1980.230492
[28] S. M. Ross,Stochastic Processes, Wiley: New York, 1983.
[29] H. L. Royden,Real Analysis, Macmillan: New York, 1968.
[30] L. Rüschendorf, ”Solution of a statistical optimization problem by rearrangement methods,”Metrika, Vol. 30, pp. 55–61, 1983. · Zbl 0535.62008 · doi:10.1007/BF02056901
[31] R. Schassberger, ”On the equilibrium distribution of a class of finite-state generalized semi-Markov processes,”Math. Oper. Res., Vol. 1, pp. 395–406, 1976. · Zbl 0363.60093 · doi:10.1287/moor.1.4.395
[32] R. Schassberger, ”Insensitivity of steady-state distributions of generalized semi-Markov processes,”Ann. Probab., Vol. 5, pp. 87–99, 1978. · Zbl 0363.60094 · doi:10.1214/aop/1176995893
[33] J. G. Shanthikumar and D. D. Yao, ”Second-order stochastic properties in queueing systems,Proc. IEEE, Vol. 77, pp. 162–170.
[34] P. W. Shor, A. Björner, and L. Lovász, ”Chip-firing games on graphs,”Euro. J. Combin., 1988, forthcoming.
[35] R. Suri, ”Perturbation analysis: The state of the art and research issues explained via the GI/G/1 queue,”Proc. IEEE, Vol. 77, pp. 114–137.
[36] P. Tsoucas and J. Walrand, ”Monotonicity of throughput in non-Markovian networks,”J. Appl. Probab., Vol. 26, pp. 134–141. · Zbl 0673.60097
[37] W. Whitt, ”Continuity of generalized semi-Markov processes,”Math. Oper. Res., Vol. 5, pp. 494–501. · Zbl 0447.60074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.