Geodesic
On the approximation of the resource equivalences in Petri nets with the invisible transitions
Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 2, pp. 234-253.

Voir la notice de l'article provenant de la source Math-Net.Ru

Two resources (submarkings) are called similar if in any marking any one of them can be replaced by another one without affecting the observable behavior of the net (regarding marking bisimulation). It is known that resource similarity is undecidable for general labelled Petri nets. In this paper we study the properties of the resource similarity and resource bisimulation (a subset of complete similarity relation closed under transition firing) in Petri nets with invisible transitions (where some transitions may be labelled with an invisible label ($\tau$) that makes their firings unobservable for an external observer). It is shown that for a proper subclass ($p$-saturated nets) the resource bisimlation can be effectively checked. For a general class of Petri net with invisible transitions it is possible to construct a sequence of so-called $(n, m)$-equivalences approximating the largest $\tau$-bisimulation of resources.
Keywords: resource, Petri nets, approximation.
Mots-clés : equivalence, invisible transitions 
@article{MAIS_2020_27_2_a6,
     author = {V. A. Bashkin},
     title = {On the approximation of the resource equivalences in {Petri} nets with the invisible transitions},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {234--253},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2020_27_2_a6/}
}
TY  - JOUR
AU  - V. A. Bashkin
TI  - On the approximation of the resource equivalences in Petri nets with the invisible transitions
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2020
SP  - 234
EP  - 253
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2020_27_2_a6/
LA  - en
ID  - MAIS_2020_27_2_a6
ER  - 
%0 Journal Article
%A V. A. Bashkin
%T On the approximation of the resource equivalences in Petri nets with the invisible transitions
%J Modelirovanie i analiz informacionnyh sistem
%D 2020
%P 234-253
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2020_27_2_a6/
%G en
%F MAIS_2020_27_2_a6
V. A. Bashkin. On the approximation of the resource equivalences in Petri nets with the invisible transitions. Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 2, pp. 234-253. http://geodesic.mathdoc.fr/item/MAIS_2020_27_2_a6/

[1] R. Milner, A Calculus of Communicating Systems, Lecture Notes in Computer Science, 92, Springer, Berlin–Heidelberg, 1980 | DOI | MR | Zbl

[2] D. Park, “Concurrency and automata on infinite sequences”, Theoretical Computer Science, Lecture Notes in Computer Science, 104, ed. P. Deussen, Springer, Berlin–Heidelberg, 1981, 167–183 | DOI | MR

[3] P. Jancar, “Decidability questions for bisimilarity of Petri nets and some related problems”, STACS 94, Lecture Notes in Computer Science, 775, eds. P. Enjalbert, E. W. Mayr, K. W. Wagner, Springer, Berlin–Heidelberg, 1994, 581–592 | DOI | MR | Zbl

[4] C. Autant, P. Schnoebelen, “Place bisimulations in Petri nets”, Application and theory of Petri Nets 1992, Lecture Notes in Computer Science, 616, ed. K. Jensen, Springer, Berlin–Heidelberg, 1992, 45-61 | DOI | MR

[5] C. Autant, W. Pfister, P. Schnoebelen, “Place bisimulations for the reduction of labeled Petri nets with silent moves”, Proc. 6th Int. Conf. on Computing and Information (Peterborough, Canada, 1994) | MR

[6] P. Schnoebelen, N. Sidorova, “Bisimulation and the reduction of Petri nets”, Application and Theory of Petri Nets, Lecture Notes in Computer Science, 1825, Springer, Berlin–Heidelberg, 2000, 409–423 | DOI | MR | Zbl

[7] V. A. Bashkin, I. A. Lomazova, “Reduction of Coloured Petri nets based on resource bisimulation”, Joint Bulletin of NCC IIS, Comp. Science, 13 (2000), 12–17 | MR

[8] V. A. Bashkin, I. A. Lomazova, “Petri nets and resource bisimulation”, Fundamenta Informaticae, 55:2 (2003), 101–114 http://iospress.metapress.com/content/NGX4LWFX81475D07 | MR | Zbl

[9] V. A. Bashkin, I. A. Lomazova, “Resource Similarities in Petri Net Models of Distributed Systems”, Parallel Computing Technologies, Lecture Notes in Computer Science, 2763, ed. V. E. Malyshkin, Springer, Berlin–Heidelberg, 2003, 35–48 | DOI | MR

[10] I. A. Lomazova, “Resource Equivalences in Petri Nets”, Application andeory of Petri Nets and Concurrency, Lecture Notes in Computer Science, 10258, ed. B. E. van der Aalst W., Springer, Berlin–Heidelberg, 2017, 19–34 | DOI | MR | Zbl

[11] V. A. Bashkin, “On the Resource Equivalences in Petri Nets with Invisible Transitions”, PNSE and Petri Nets 2017, CEUR-WS, 1846, 2017, 51–68

[12] L. Redei, The theory ofnitely generated commutative semigroups, Oxford University Press, 1965 | MR

[13] Y. Hirshfeld, Congruences in commutative semigroups, Research Report ECS-LFCS-94-291, University of Edinburgh, Department of Computer Science, Edinburgh, 1994