Geodesic
Remarks on the reachability graphs of Petri nets
Modelirovanie i analiz informacionnyh sistem, Tome 29 (2022) no. 4, pp. 366-371.

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

The question is considered - which graphs are isomorphic to the reachability graphs of Petri nets. Reachability graphs, or sets of achievable states, represent sets of all possible different network states resulting from a given initial state s$_{0}$ by a finite chain of permissible transitions. They have a natural structure of an oriented graph with a dedicated initial state, all other states of which are reachable from the initial one, taking into account orientation. At the same time, if the network transitions are marked, the reachability graphs also receive the corresponding marks of all arcs. At the same time, the concept of isomorphism of marked graphs arises, but this publication deals only with issues for networks without markings. Even for this simpler case, some questions remain open. The paper proves that any finite directed graph is modeled by a suitable Petri net, that is, it is isomorphic to the reachability graph of the network. For infinite graphs, examples of non-modeled graphs are given.
Keywords: Petri nets, network reachability graph, network coverage graph
Mots-clés : graph isomorphism. 
@article{MAIS_2022_29_4_a4,
     author = {Yu. A. Belov},
     title = {Remarks on the reachability graphs of {Petri} nets},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {366--371},
     publisher = {mathdoc},
     volume = {29},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2022_29_4_a4/}
}
TY  - JOUR
AU  - Yu. A. Belov
TI  - Remarks on the reachability graphs of Petri nets
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2022
SP  - 366
EP  - 371
VL  - 29
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2022_29_4_a4/
LA  - ru
ID  - MAIS_2022_29_4_a4
ER  - 
%0 Journal Article
%A Yu. A. Belov
%T Remarks on the reachability graphs of Petri nets
%J Modelirovanie i analiz informacionnyh sistem
%D 2022
%P 366-371
%V 29
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2022_29_4_a4/
%G ru
%F MAIS_2022_29_4_a4
Yu. A. Belov. Remarks on the reachability graphs of Petri nets. Modelirovanie i analiz informacionnyh sistem, Tome 29 (2022) no. 4, pp. 366-371. http://geodesic.mathdoc.fr/item/MAIS_2022_29_4_a4/

[1] W. Reisig, Petri nets. an introduction, Springer-Verlag, New York, 1985

[2] V. E. Kotov, Petri nets, Nauka, M., 1984

[3] M. Diaz, Petri nets: fundamental models, verification and applications, J. Wiley, Inc. USA, 2009

[4] H.-C. Yen, “Introduction to petri net theory”, Recent Advances in Formal Languages and Applications, 25, Springer, 2006, 343–373

[5] E. V. Kuzmin, V. A. Sokolov, Automata counter machines, P.G. Demidov Yaroslavl State University, 2012

[6] V. A. Evstigneev, V. N. Kasianov, Teoria grafov. Algoritmy obrabotki dereview, Nauka, Novosibirsk, 1984