Инверсия простой ординарной сети Петри

ISSN , http://journals. *****/vestnik
Научный вестник НГТУ	Scientific Bulletin of NSTU
том 53, № 4, 2013, с. 215-219	Vol. 53, No. 4, 2013, pp.215-219

современные информационные технологии

(Modern information technologies)

УДК 62-83: 531.3

Инверсия простой ординарной сети Петри*

А. А. воевода1, 2, 3 СОРТИРОВКА ФАМИЛИй по алфавиту

1 РФ, г. Новосибирск, пр. Карла Маркса, 20, Новосибирский государственный технический университет, д. т.н., профессор, e-mail: [e-mail]

2 РФ, г. Красноярск, пр. Ленина, 14, Сибирский Федеральный университет,

аспирант, e-mail: *****@***ru

1 РФ, г. Новосибирск, пр. Карла Маркса, 20, Новосибирский государственный технический университет, д. т.н., профессор, e-mail: [e-mail]

Аннотация должна отражать актуальность исследования, цель исследования, методы исследования, результаты исследования. В данной работе приводится описание аппарата сетей Петри, предлагается математическое определение простой ординарной сети Петри, как наиболее простого вида из всех возможных вариантов сетей. Перечислены способы анализа, как традиционные: построение дерева достижимости, матричное представление сети, генерация отчёта о пространстве состояний, так и нетрадиционные: sweep-line method, bitstate hashing. Описано одно из основных свойств сетей Петри – достижимость. Обоснована его актуальность и необходимость подтверждения данного свойства у определенных состояний. Доказательство достижимости предлагается реализовать при помощи инверсии системы, которая заключается в изменении структуры сети и приводит к получению начальной маркировки, что свидетельствует о достижимости маркировки, с которой началась инверсия. Для доказательства достижимости маркировки предлагается реализовать инверсию сети, которая заключается в изменении направления всех взаимосвязей системы на противоположное. Это приведёт к движению фишек в обратном направлении и тем самым к начальному состоянию сети. Реализацию инверсии сети с последующим построением дерева достижимости, предлагается осуществить по предложенному алгоритму. В заключении представлены основные результаты работы и её последующее развитие: разработка правил для реализации инверсии у простых сетей Петри. Это приведёт к движению фишек в обратном направлении и тем самым к начальному состоянию сети. Реализацию инверсии сети с последующим построением дерева достижимости, предлагается осуществить по предложенному алгоритму. В заключении представлены основные результаты работы и её последующее развитие: разработка правил для реализации инверсии у простых сетей Петри. АННОТАЦИЯ 200-250 СЛОВ

Ключевые слова: сети Петри, простая ординарная сеть Петри, дерево достижимости, пространство состояний, достижимость, начальная маркировка, инверсия, прямая инверсия КЛЮЧЕВЫХ СЛОВ от 8 до 16 (ОДНО СЛОВОСОЧЕТАНИЕ = ОДНО СЛОВО)

Введение

Сетью Петри – двудольный ориентированный граф, состоящий из вершин двух типов: мест и переходов, взаимосвязанных между собой дугами [1]. По сети могут передвигаться метки при срабатывании переходов, которые символизируют всевозможные ресурсы системы.

Самыми первыми и самыми простыми являются простые ординарные сети Петри (ПОСП) – упорядоченное множество , где – множество мест, а – множество переходов, таких что , – взаимосвязь вершин, и [2].

На сегодняшний день разработаны следующие виды анализа спроектированных сетей: построение дерева достижимости, матричное представление сети, а также генерация отчета о пространстве состояний при помощи среды моделирования CPN Tools (version 3.4.0) [3–6].

Также существуют нестандартные подходы к анализу систем, т. е. методики, использующие иные алгоритмы по отношению к традиционному. К ним относятся sweep-line method, bitstate hashing и их возможные модификации. Достоинством представленных методов является анализ систем с пространством состояний огромных размеров, но явный недостаток – это возможность частичного покрытия пространства состояний.

Во время моделирования может встать вопрос о проверке достижимости полученной маркировки с целью начать анализ системы с выбранного состояния или исследовать граф достижимости по частям [5]. Следовательно, доказательство данного свойства является актуальной задачей.

В данной работе предлагается способ доказательства достижимости выбранного состояния, если заранее неизвестно попадает ли оно в пространство состояний всей системы, а известна только начальная маркировка сети.

ИНВЕРСИЯ

Для доказательства достижимости маркировки предлагается реализовать инверсию сети, которая заключается в изменении направления всех взаимосвязей системы на противоположное. Это приведёт к движению фишек в обратном направлении и тем самым к начальному состоянию сети.

Рис. 1. Система, состоящая из двух мест: слева – сеть Петри и её дерево достижимости, справа – инвертированная сеть Петри и ее дерево достижимости cpn

Покажем данную операцию на системе, состоящей из двух мест и одного перехода (рис. 1, слева). После чего инвертируем представленную модель (рис. 1, справа). В инвертированной модели система попадает в состояние № 2 (рис. 1, справа), которое является начальной маркировкой системы.

Алгоритм 1. Инверсия простой ординарной сети Петри и вычисление дерева достижи-мости:

Реализацию инверсии ПОСП с вычислением пространства состояний можно представить в виде последовательности действий (алгоритм 1).

Используя алгоритм, представленный выше, нужно помнить, что прямая инверсия возможна только для ПОСП. При наличии условий у переходов и дуг (простая сеть Петри) стоит ввести определенный набор правил.

Рис. 2. Небольшая простая сеть Петри (слева), после инверти-рования (справа) cpn

Несмотря на усложнение сети Петри (рис. 2, слева), структура которой , , , , , а дерево достижимости: , , , , , возможна прямая инверсия сети. После чего получаем систему (рис. 2, справа): , , , , , в которой сохраняется структура пространстве состояний: , , , , , и присутствует возможность нахождения начального состояния системы: .

ЗАКЛЮЧЕНИЕ

В данной работе приводится описание свойства достижимости – одного из основных свойств сетей Петри, которое необходимо для проверки нахождения выбранного состояния во всём пространстве состояний системы. Для доказательства достижимости предлагается применить инверсию системы, которая заключается в изменении ориентации дуг между вершинами сети. Инверсия реализована на примере простой ординарной и простой сетях Петри.

Стоит уточнить, что для простой ординарной сети подходит прямая инверсия. Для простых сетей Петри, в свою очередь, стоит добавить ряд правил, описание которых будет предложено в последующих работах. Проверка предложенных правил будет реализована на сети, которая является классической задачей, а именно «Протокола передачи данных».

СПИСОК ЛИТЕРАТУРЫ минимум от 10 источников

[1]  ZHU Lian-Zhanga, KONG Fan-Sheng. Automatic Conversion from UML to CPN for Software Performance Evaluation // Procedia Engineering. – 2012. – No. 29. – P. 2682–2686.

[2]  Campos J., Merseguer J. On the Integration of UML and Petri Nets in Software Development // ICATPN. – 2006. – P. 19–36.

[3]  Yann Thierry-Mieg, Lom-Messan Hillah. UML behavioral consistency checking using instantiable Petri nets // Innovations Syst Softw Eng. – 2008. – No. 4. – P. 293–300.

[4]  Eichner C., Fleischhack H., Meyer R., Schrimpf U., Stehno C. Compositional Semantics for UML 2.0 Sequence Diagrams Using Petri Nets // SDL. – 2005. – P. 133–148.

[5]  Nianhua Yang, Huiqun Yu, Hua Sun, Zhilin Qian. Modeling UML sequence diagrams using extended Petri nets // Telecommun Syst. – 2012. – Vol. 51. – P. 147–158.

[6]  Basile F., Chiacchio P., Grosso D. D. A two-stage modelling architecture for distributed control of real-time industrial systems: Application of UML and Petri Net // Computer Standards & Interfaces. – 2009. – Vol. 31. – P. 528–538.

[7]  Miyamoto T., Kurahata H., Fujii T., Hosokawa R. Synthesis of state machine diagrams from communication diagrams using Petri nets // Innovations Syst Softw Eng. – 2010. – Vol. 6. – P. 39–46.

[8]  Применение сетей Петри в разработке программного обеспечения центров дистанционного контроля и управления. – Диссертация …. канд. техн. наук. – Новосибирск: 2007.

[9]  , Пример применения методики разработки ПО с использованием UML-диаграмм и сетей Петри // Научный вестник НГТУ. – 2012. – №1(67). – С. 175–181.

[10]  , . Применение UML диаграмм и сетей Петри при разработке встраиваемого программного обеспечения // Науч. вестн. НГТУ. - 2009. - №4 (37). - с. 169-174.

[11]  , Развитие системы “Перемещение манипулятора в пространстве с препятствиями” при помощи рекурсивных функций // Автоматика и программная инженерия. – 2013. – № 2. – С. 35–41.

[12]  , Анализ сетей Петри при помощи деревьев достижимости // Сборник научных трудов НГТУ. – 2013. - № 1. – С. 78–95.

, доктор технических наук, профессор Новосибирского государственного технического университета. Основное направление научных исследований – теория автоматического управления, сети Петри. Имеет более 200 публикаций. E-mail: [e-mail]

, магистр техники и технологии, аспирант кафедры автоматики Новосибирского государственного технического университета. Основное направление научных исследований – сети Петри. Имеет более 20 публикаций. E-mail: *****@***ru

, к. т.н., старший преподаватель Новосибирского государственного технического университета. Основное направление научных исследований – сети Петри. Имеет более 20 публикаций. E-mail: *****@***ru

ISSN , http://journals. *****/vestnik

Scientific Bulletin of NSTU

Vol. 53, No. 4, 2013, pp.215-219

Inversion of simple ordinary Petri nets*

A. Voevoda1 , A. Markov2, D. Romannikov3

1 Novosibirsk state technical University, 20 prospect Karla Marksa, Novosibirsk, Russian Federation, doctor of technical Sciences, Professor, e-mail: *****@***ru

2 Siberian Federal University,14 Lenina street, , Krasnoyarsk, Russian Federation,

post-graduate student, e-mail: *****@***ru

3 Novosibirsk state technical University, 20 prospect Karla Marksa, Novosibirsk, Russian Federation, doctor of technical Sciences, Professor, e-mail: *****@***ru

In this paper we describe Petri nets, proposed is a mathematical definition of simple ordinary Petri nets, as the most simple form of all possible nets. Methods of analysis are listed as traditional: tree building reachability, matrix representation of the net, report generation space states and non-traditional: sweep-line method, bit-state hashing. Described one of the fundamental properties of Petri nets – reachability. Proved its relevance and the need to confirm this property in certain states. Reachability proof offered implemented using the inversion system, which is to change the structure and results in the initial marking, indicating that the attainability of the mark, which began inversion. Terms of inversion are shown in a net consisting of two places, one of which contains a single chip, and one transition Implementation of net inversion followed by the construction of tree reachability, are proposed by the proposed algorithm, which began inversion. Terms of inversion are shown in a net consisting of two places, one of which contains a single chip, and one transition Implementation of net inversion followed by the construction of tree reachability, are proposed by the proposed algorithm, which began inversion. Terms of inversion are shown in a net consisting of two places, one of which contains a single chip, and one transition Implementation of net inversion followed by the construction of tree reachability, are proposed by the proposed algorithm In conclusion, the main results of the work and its subsequent development: the development of rules for the implementation of the inversion from ordinary Petri nets. Terms of inversion are shown in a net consisting of two places, one of which contains a single chip, and one transition Implementation of net inversion followed by the construction of tree reachability, are proposed by the proposed algorithm, which began inversion. Terms of inversion are shown in a net consisting of two places, one of which contains a single chip, and one transition Implementation of net inversion followed by the construction of tree reachability, are proposed by the proposed algorithm In conclusion, the main results of the work and its subsequent development: the development of rules for the implementation of the inversion from ordinary Petri nets.

Keywords: Petri nets, Petri net just any, tree reachable, state space, accessibility, initial marking, inversion, direct inversion

REFERENCES

[1]  ZHU Lian-Zhanga, KONG Fan-Sheng. Automatic Conversion from UML to CPN for Software Performance Evaluation. Procedia Engineering, 2012, no.29, pp.2682–2686.

[2]  Campos J., Merseguer J. On the Integration of UML and Petri Nets in Software Development. ICATPN, 2006, pp.19–36.

[3]  Yann Thierry-Mieg, Lom-Messan Hillah. UML behavioral consistency checking using instantiable Petri nets. Innovations Syst Softw Eng., 2008, no.4, pp.293–300.

[4]  Eichner C., Fleischhack H., Meyer R., Schrimpf U., Stehno C. Compositional Semantics for UML 2.0 Sequence Diagrams Using Petri Nets. SDL, 2005, pp.133–148.

[5]  Nianhua Yang, Huiqun Yu, Hua Sun, Zhilin Qian. Modeling UML sequence diagrams using extended Petri nets. Telecommun Syst., 2012, vol.51, pp.147–158.

[6]  Basile F., Chiacchio P., Grosso D. D. A two-stage modelling architecture for distributed control of real-time industrial systems: Application of UML and Petri puter Standards & Interfaces, 2009, vol.31, pp.528–538.

[7]  Miyamoto T., Kurahata H., Fujii T., Hosokawa R. Synthesis of state machine diagrams from communication diagrams using Petri nets. Innovations Syst Softw Eng., 2010, vol.6, pp.39–46.

[8]  Korotikov S. V. Application of Petri nets in software development centers, remote monitoring and control. – Thesis …. candidate tehn. sciences. – Novosibirsk: 2007.

[9]  Romannikov D. O., Markov A. V. Example application of the methodology of software development using UML-diagrams and Petri nets. Scientific Bulletin of NSTU, 2012, no.1(67), pp. 175–181.

[10]  Voevoda A. A., Romannikov D. O. Applying UML diagrams and Petri nets in developing embedded software. Scientific Bulletin of NSTU, 2009, no.4 (37), pp.169-174.

[11]  Markov A. V., Voevoda A. A. Development of the system "Moving the manipulator in space with obstacles" using recursive functions. Avtomatika i programmnaja inzhenerija. – 2013. – № 2. – P. 35–41.

[12]  Markov A. V., Voevoda A. A. Analysis of Petri nets by means of reachability trees. Sbornik nauchnyh trudov NGTU.– 2013. - № 1. – P. 78–95.

* Статья получена 01 июля 2013 г.

Работа выполнена при поддержке Министерства образования и науки Российской Федерации, проект
№ 7.559.2011, гос. рег. номер НИР

*Manuscript received on July 1, 2013.

The work was supported by the Ministry of education and science of the Russian Federation, project no 7.559.2011, state registration number of scientific research works