Марков Александр Владимирович,
Воевода Александр Александрович
Аннотация
В данной работе приводится описание аппарата сетей Петри, предлагается математическое определение простой ординарной сети Петри, как наиболее простого вида из всех возможных вариантов сетей. Перечислены способы анализа, как традиционные: построение дерева достижимости, матричное представление сети, генерация отчёта о пространстве состояний, так и нетрадиционные: sweep-line method, bitstate hashing. Описано одно из основных свойств сетей Петри – достижимость. Обоснована его актуальность и необходимость подтверждения данного свойства у определенных состояний. Доказательство достижимости предлагается реализовать при помощи инверсии системы, которая заключается в изменении структуры сети и приводит к получению начальной маркировки, что свидетельствует о достижимости маркировки, с которой началась инверсия. Реализацию инверсии сети с последующим построением дерева достижимости, предлагается осуществить по предложенному алгоритму. В заключении представлены основные результаты работы и её последующее развитие: разработка правил для реализации инверсии у простых сетей Петри.
Ключевые слова: сети Петри, простая ординарная сеть Петри, дерево достижимости, пространство состояний, достижимость, начальная маркировка, инверсия, прямая инверсия
Авторы:
Марков Александр Владимирович
магистр техники и технологии, аспирант кафедры автоматики Новоси-бирского государственного технического университета. Основное направление научных исследований – сети Петри. Имеет более 20 публикаций. E-mail: ucit@ucit.ru
Воевода Александр Александрович
доктор технических наук, профессор. Основное направление научных исследований – теория автоматического управления, сети Петри. Имеет более 200 публикаций. E-mail: ucit@ucit.ru
Список литературы
[1] Питерсон Дж. Теория сетей Петри и моделирование: пер. с англ. / Дж. Питерсон. – М.: Мир, 1984. [2] Westergaard M. Behavioral verification and visualization of formal models of concurrent systems: PhD dissertation / M. Westergaard. – Aarhus: University of Aarhus, 2007. [3] Марков А.В. Моделирование процесса поиска пути в лабиринте при помощи сетей Петри / А.В. Марков. // Сб. науч. тр. НГТУ. – 2010. – № 4(62). – С. 133–141. [4] Романников Д.О. Пример применения методики разработки ПО с использованием UML-диаграмм и сетей Петри / Д.О. Романников, А.В. Марков // Научный вестник НГТУ. – 2012. – № 1(67). – С. 175–181. [5] Марков А.В. Анализ сетей Петри при помощи деревьев достижимости / А.В. Марков, А.А. Воевода // Сб. науч. тр. НГТУ. – 2013. – № 1(71). – С. 78–95. [6] Марков А.В. Матричное представление сетей Петри / А.В. Марков // Сб. науч. тр. НГТУ. – 2013. – № 2(71). – С. 61–67. [7] Christensen S. A sweep-line method for state space exploration / S. Christensen, L.M. Kristensen, T. Mailund // Springer-Verlag Berlin Heidelberg. – 2001. – P. 450–464. [8] Holzmann G.J. An analysis of bitstate hashing / G.J. Holzmann // Symposium on Protocol Specification. – 1995. – № 15. – P. 301–314.
