|
Algorithms
Замечания о графах достижимости сетей Петри
Ю. А. Белов Ярославский государственный университет им. П. Г. Демидова, ул. Советская, д. 14, г. Ярославль, 150003 Россия
Аннотация:
Рассматривается вопрос - какие графы изоморфны графам достижимости сетей Петри. Графы достижимости, или множества достижимых состояний, представляют множества всевозможных различных состояний сети, получающихся из данного начального состояния s$_{0}$ конечной цепочкой допустимых переходов. Они имеют естественную структуру ориентированного графа с выделенным начальным состоянием, все другие состояния которого достижимы из начального с учётом ориентации. При этом, если переходы сети снабжены пометками, графы достижимости также получают соответствующие пометки всех дуг. При этом возникает понятие изоморфизма размеченных графов, но в данной публикации рассматриваются лишь вопросы для сетей без разметок. Даже для этого более простого случая некоторые вопросы остаются открытыми.
В заметке доказывается, что любой конечный ориентированный граф моделируется подходящей сетью Петри, то есть он изоморфен графу достижимости сети. Для бесконечных графов приводятся примеры не моделируемых графов. Ставятся некоторые открытые вопросы по теме.
Ключевые слова:
сети Петри, граф достижимости сети, граф покрытия сети, изоморфизм графов.
Поступила в редакцию: 07.10.2022 Исправленный вариант: 28.11.2022 Принята в печать: 30.11.2022
Образец цитирования:
Ю. А. Белов, “Замечания о графах достижимости сетей Петри”, Модел. и анализ информ. систем, 29:4 (2022), 366–371
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais785 https://www.mathnet.ru/rus/mais/v29/i4/p366
|
Статистика просмотров: |
Страница аннотации: | 76 | PDF полного текста: | 34 | Список литературы: | 10 |
|