maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2022-4-366-371mais-1752Research ArticleAlgorithmsЗамечания о графах достижимости сетей ПетриRemarks on the Reachability Graphs of Petri Netshttps://orcid.org/0000-0002-4221-6470БеловЮрий АнатольевичBelovYuriy Anatol’yevichbelov45@yandex.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation202218122022294366371Copyright © Белов Ю.А., 20222022Белов Ю.А.Belov Y.A.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1752

Рассматривается вопрос - какие графы изоморфны графам достижимости сетей Петри. Графы достижимости, или множества достижимых состояний, представляют множества всевозможных различных состояний сети, получающихся из данного начального состояния s0 конечной цепочкой допустимых переходов. Они имеют естественную структуру ориентированного графа с выделенным начальным состоянием, все другие состояния которого достижимы из начального с учётом ориентации. При этом, если переходы сети снабжены пометками, графы достижимости также получают соответствующие пометки всех дуг. При этом возникает понятие изоморфизма размеченных графов, но в данной публикации рассматриваются лишь вопросы для сетей без разметок. Даже для этого более простого случая некоторые вопросы остаются открытыми. В заметке доказывается, что любой конечный ориентированный граф моделируется подходящей сетью Петри, то есть он изоморфен графу достижимости сети. Для бесконечных графов приводятся примеры не моделируемых графов. Ставятся некоторые открытые вопросы по теме.

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.

сети Петриграф достижимости сетиграф покрытия сетиизоморфизм графовPetri netsnetwork reachability graphnetwork coverage graphgraph isomorphismReferencesW. Reisig, Petri Nets. An Introduction. Springer-Verlag, New York, 1985.W. Reisig, Petri Nets. An Introduction. Springer-Verlag, New York, 1985.V. E. Kotov, Petri Nets, in Russian. Moscow, Nauka, 1984.V. E. Kotov, Petri Nets, in Russian. Moscow, Nauka, 1984.M. Diaz, Petri Nets: Fundamental Models, Verification and Applications. J. Wiley, Inc. USA, 2009.M. Diaz, Petri Nets: Fundamental Models, Verification and Applications. J. Wiley, Inc. USA, 2009.H.-C. Yen, "Introduction to Petri Net Theory”, Recent Advances in Formal Languages and Applications, vol. 25, pp. 343-373, 2006.H.-C. Yen, "Introduction to Petri Net Theory”, Recent Advances in Formal Languages and Applications, vol. 25, pp. 343-373, 2006.E. V. Kuzmin and V. A. Sokolov, Automata Counter Machines, in Russian. P.G. Demidov Yaroslavl State University, 2012.E. V. Kuzmin and V. A. Sokolov, Automata Counter Machines, in Russian. P.G. Demidov Yaroslavl State University, 2012.V. A. Evstigneev and V. N. Kasianov, Teoria Grafov. Algoritmy obrabotki dereview, in Russian. Nauka, Novosibirsk, 1984.V. A. Evstigneev and V. N. Kasianov, Teoria Grafov. Algoritmy obrabotki dereview, in Russian. Nauka, Novosibirsk, 1984.

The authors declare that there are no conflicts of interest present.