Remarks on the Reachability Graphs of Petri Nets
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 s0 by a finite chain of permissible transitions. They hav...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2022-12-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1752 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849240976358375424 |
|---|---|
| author | Yuriy Anatol’yevich Belov |
| author_facet | Yuriy Anatol’yevich Belov |
| author_sort | Yuriy Anatol’yevich Belov |
| collection | DOAJ |
| description | 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 s0 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. |
| format | Article |
| id | doaj-art-a5fb46eb0a7e4a5a85bc99ea77633a20 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2022-12-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-a5fb46eb0a7e4a5a85bc99ea77633a202025-08-20T04:00:19ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172022-12-0129436637110.18255/1818-1015-2022-4-366-3711357Remarks on the Reachability Graphs of Petri NetsYuriy Anatol’yevich Belov0P. G. Demidov Yaroslavl State UniversityThe 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 s0 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.https://www.mais-journal.ru/jour/article/view/1752petri netsnetwork reachability graphnetwork coverage graphgraph isomorphism |
| spellingShingle | Yuriy Anatol’yevich Belov Remarks on the Reachability Graphs of Petri Nets Моделирование и анализ информационных систем petri nets network reachability graph network coverage graph graph isomorphism |
| title | Remarks on the Reachability Graphs of Petri Nets |
| title_full | Remarks on the Reachability Graphs of Petri Nets |
| title_fullStr | Remarks on the Reachability Graphs of Petri Nets |
| title_full_unstemmed | Remarks on the Reachability Graphs of Petri Nets |
| title_short | Remarks on the Reachability Graphs of Petri Nets |
| title_sort | remarks on the reachability graphs of petri nets |
| topic | petri nets network reachability graph network coverage graph graph isomorphism |
| url | https://www.mais-journal.ru/jour/article/view/1752 |
| work_keys_str_mv | AT yuriyanatolyevichbelov remarksonthereachabilitygraphsofpetrinets |