Geodesic
Equivalences for stochastic Petri nets and stochastic process algebras
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 6 (2006) no. 1, pp. 14-42 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A new class of stochastic Petri nets (SPNs) is proposed that is a modification of discrete time SPNs (DTSPNs) by transition labeling. The class is called labeled DTSPNs (LDT- SPNs). The observable behavior of a LDTSPN is described by labeling of transitions with actions that represent elementary activities. The dynamic behavior of LDTSPNs is defined, and the corresponding discrete time Markov chain (DTMC) is constructed. Behavioural equivalences of LDTSPNs are introduced as variants of well-known trace and bisimulation relations. Interrelations of all the mentioned equivalence relations are investigated. A logical characterization of the equivalences is presented via formulas of probabilistic modal logics. It is demonstrated how the equivalences can be used to compare stationary behavior of LDT-SPNs. A stochastic process algebra is proposed with formulas specifying a special subclass of LDTSPNs. 
@article{VNGU_2006_6_1_a1,
     author = {P. Buchholz and I. V. Tarasyuk},
     title = {Equivalences for stochastic {Petri} nets and stochastic process algebras},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {14--42},
     year = {2006},
     volume = {6},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2006_6_1_a1/}
}
TY  - JOUR
AU  - P. Buchholz
AU  - I. V. Tarasyuk
TI  - Equivalences for stochastic Petri nets and stochastic process algebras
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2006
SP  - 14
EP  - 42
VL  - 6
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VNGU_2006_6_1_a1/
LA  - ru
ID  - VNGU_2006_6_1_a1
ER  - 
%0 Journal Article
%A P. Buchholz
%A I. V. Tarasyuk
%T Equivalences for stochastic Petri nets and stochastic process algebras
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2006
%P 14-42
%V 6
%N 1
%U http://geodesic.mathdoc.fr/item/VNGU_2006_6_1_a1/
%G ru
%F VNGU_2006_6_1_a1
P. Buchholz; I. V. Tarasyuk. Equivalences for stochastic Petri nets and stochastic process algebras. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 6 (2006) no. 1, pp. 14-42. http://geodesic.mathdoc.fr/item/VNGU_2006_6_1_a1/

[1] A. Aziz, V. Singhal, F. Balarin, R. K. Brayton, A. L. Sangiovanni-Vincentelli, “It usually works: the temporal logic of stochastic systems”, Lect. Notes Comp. Sci., 939 (1995), 155–165 | DOI

[2] E. Best, R. Devillers, “Sequential and concurrent behaviour in Petri net theory”, Theoretical Computer Sci., 55 (1987), 87–136 | DOI | MR | Zbl

[3] E. Best, R. Devillers, J. G. Hall, “The box calculus: a new causal algebra with multi-label communication”, Lect. Notes Comp. Sci., 609, 1992, 21–69 | DOI | MR

[4] C. Baier, H. Hermanns, “Weak bisimulation for fully probabilistic processes”, Lect. Notes Comp. Sci., 1254, 1997, 119–130 | DOI

[5] C. Baier, H. Hermanns, J.-P. Katoen, V. Wolf, “Comparative branching-time semantics for Markov chains”, Lect. Notes Comp. Sci., 2761, 2003, 492–507 | DOI | MR | Zbl

[6] P. Buchholz, I. V. Tarasyuk, “Net and algebraic approaches to probablistic modeling”, Joint Novosibirsk Computing Center and Institute of Informatics Systems Bulletin, Series Computer Science, 15 (2001), 31–64 http://www.iis.nsk.su/persons/itar/spnpancc.pdf | MR | Zbl

[7] P. Buchholz, “Markovian process algebra: composition and equivalence”, Proc. of 2$^{nd}$ Workshop on Process Algebras and Performance Modelling (University of Erlangen, Germany, 1994), Arbeitsberichte des IMMD, 27, 11–30

[8] P. Buchholz, “Equivalence relations for stochastic automata networks”, Computation with Markov Chains, ed. Stewart W. J., Kluwer, 1995, 197–216 | DOI

[9] P. Buchholz, “A notion of equivalence for stochastic Petri nets”, Lect. Notes Comp. Sci., 935, 1995, 161–180 | DOI | MR

[10] P. Buchholz, “Iterative decomposition and aggregation of labeled GSPNs”, Lect. Notes Comp. Sci., 1420, 1998, 226–245 | DOI

[11] P. Buchholz, “Exact performance equivalence — an equivalence relation for stochastic automata”, Theoretical Computer Sci., 215:1/2 (1999), 263–287 | DOI | MR | Zbl

[12] L. A. Cherkasova, Posets with non-actions: a model for concurrent nondeterministic processes, Arbeitspapiere der GMD 403, Germany, 1989, 68 pp.

[13] I. Christoff, “Testing equivalence and fully abstract models of probabilistic processes”, Lect. Notes Comp. Sci., 458, 1990, 128–140 | MR

[14] F. Cherief, F. Laroussinie, S. Pinchinat, Modal logics with past for true concurrency, Internal Report, LIFIA, Institut National Polytechnique, Grenoble, France, 1992

[15] R. Cleaveland, J. Parrow, B. Steffen, “The concurrency workbench: a semantics based tool for the verification of concurrent systems”, ACM Transactions on Programming Languages and Systems, 15:1 (1993), 36–72 | DOI

[16] G. Florin, S. Natkin, “Les reseaux de Petri stochastiques”, Technique et Science Informatique, 4:1 (1985), 143–160 | Zbl

[17] M. Hennessy, R. A. J. Milner, “Algebraic laws for non-determinism and concurrency”, Journal of the ACM, 32:1 (1985), 137–161 | DOI | MR | Zbl

[18] K. G. Larsen, A. Skou, “Bisimulation through probabilistic testing”, Information and Computation, 94:1 (1991), 1–28 | DOI | MR | Zbl

[19] M. A. Marsan, G. Conte, G. Balbo, “A class of generalized stochastic Petri nets for performance evaluation of multiprocessor systems”, ACM Transactions on Computer Systems, 2:2 (1984), 93–122 | DOI

[20] M. Majster-Cederbaum, J. Wu, “Adding action refinement to stochastic true concurrency models”, Lect. Notes Comp. Sci., 2885, 2003, 226–245 | DOI

[21] M. Molloy, “Performance analysis using stochastic Petri nets”, IEEE Transactions on Computing, 31:9 (1982), 913–917 | DOI

[22] M. Molloy, “Discrete time stochastic Petri nets”, IEEE Transactions on Software Engineering, 11:4 (1985), 417–423 | DOI | MR | Zbl

[23] R. De Nicola, U. Montanari, F. W. Vaandrager, “Back and forth bisimulations”, Lect. Notes Comp. Sci., 458, 1990, 152–165 | DOI | MR

[24] H. S. Macia, V. R. Valero, D. E. de Frutos, “sPBC: a Markovian extension of finite Petri box calculus”, Proc. of 9 th IEEE International Workshop on Petri Nets and Performance Models — 01 (PNPM'01) (Aachen, Germany), IEEE Computer Society Press, 2001, 207–216 http://www.inf-ab.uclm.es/fmc/publications/2001/pnpm01.ps | DOI

[25] S. Pinchinat, Bisimulations for the semantics of reactive systems, Ph. D. thesis, Institut National Politechnique de Grenoble, 1993 (in French)

[26] L. Pomello, G. Rozenberg, C. Simone, “A survey of equivalence notions for net based systems”, Lect. Notes Comp. Sci., 609, 1992, 410–472 | DOI | MR

[27] R. Zijal, R. German, “A new approach to discrete time stochastic Petri nets”, Lecture Notes in Control and Information Science, 199, 1994, 198–204 | DOI