Замечания о графах достижимости сетей Петри
https://doi.org/10.18255/1818-1015-2022-4-366-371
Аннотация
Рассматривается вопрос - какие графы изоморфны графам достижимости сетей Петри. Графы достижимости, или множества достижимых состояний, представляют множества всевозможных различных состояний сети, получающихся из данного начального состояния s0 конечной цепочкой допустимых переходов. Они имеют естественную структуру ориентированного графа с выделенным начальным состоянием, все другие состояния которого достижимы из начального с учётом ориентации. При этом, если переходы сети снабжены пометками, графы достижимости также получают соответствующие пометки всех дуг. При этом возникает понятие изоморфизма размеченных графов, но в данной публикации рассматриваются лишь вопросы для сетей без разметок. Даже для этого более простого случая некоторые вопросы остаются открытыми. В заметке доказывается, что любой конечный ориентированный граф моделируется подходящей сетью Петри, то есть он изоморфен графу достижимости сети. Для бесконечных графов приводятся примеры не моделируемых графов. Ставятся некоторые открытые вопросы по теме.
Список литературы
1. W. Reisig, Petri Nets. An Introduction. Springer-Verlag, New York, 1985.
2. V. E. Kotov, Petri Nets, in Russian. Moscow, Nauka, 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, vol. 25, pp. 343-373, 2006.
5. E. V. Kuzmin and V. A. Sokolov, Automata Counter Machines, in Russian. P.G. Demidov Yaroslavl State University, 2012.
6. V. A. Evstigneev and V. N. Kasianov, Teoria Grafov. Algoritmy obrabotki dereview, in Russian. Nauka, Novosibirsk, 1984.
Рецензия
Для цитирования:
Белов Ю.А. Замечания о графах достижимости сетей Петри. Моделирование и анализ информационных систем. 2022;29(4):366-371. https://doi.org/10.18255/1818-1015-2022-4-366-371
For citation:
Belov Yu.A. Remarks on the Reachability Graphs of Petri Nets. Modeling and Analysis of Information Systems. 2022;29(4):366-371. (In Russ.) https://doi.org/10.18255/1818-1015-2022-4-366-371
Просмотров: 305
Послать статью по эл. почте 