Preview

Моделирование и анализ информационных систем

Расширенный поиск

Метод генерации примеров моделей программ в терминах сетей Петри

https://doi.org/10.18255/1818-1015-2015-4-563-577

Аннотация

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

Об авторах

Д. И. Харитонов
Федеральное государственное бюджетное учреждение науки Институт автоматики и процессов управления Дальневосточного отделения РАН
Россия

канд. техн. наук, ст. науч. сотр.

ул. Радио, д. 5, г. Владивосток, Россия, 690041



Е. А. Голенков
Федеральное государственное бюджетное учреждение науки Институт автоматики и процессов управления Дальневосточного отделения РАН
Россия

канд. физ.-мат. наук, ст. науч. сотр

ул. Радио, д. 5, г. Владивосток, Россия, 690041



Г. В. Тарасов
Федеральное государственное бюджетное учреждение науки Институт автоматики и процессов управления Дальневосточного отделения РАН Дальневосточный Федеральный Университет
Россия

 науч. сотр. ул. Радио, д. 5, г. Владивосток, Россия, 690041

 науч. сотр. ул. Суханова, д. 8, г. Владивосток, Россия, 690950

 



Д. В. Леонтьев
Федеральное государственное бюджетное учреждение науки Институт автоматики и процессов управления Дальневосточного отделения РАН Дальневосточный Федеральный Университет
Россия

 науч. сотр. ул. Радио, д. 5, г. Владивосток, Россия, 690041

 науч. сотр. ул. Суханова, д. 8, г. Владивосток, Россия, 690950



Список литературы

1. Peterson, James Lyle, Petri Net Theory and the Modeling of Systems, Prentice Hall, 1981, 290 pp.

2. Anisimov N.A., Kovalenko A.A., “Towards Petri Net Calculi based on Synchronization via Places”, Proc. of the 1995 IEEE Symposium on Parallel Algorithms/Architecture Synthesis, IEEE Press, Japan, 1995, 264–270.

3. Best, Eike and Devillers, Raymond and Koutny, Maciej, Petri Net Algebra, Springer-erlag New York, Inc., USA, 2001.

4. International Atomic Energy Agency, A Panel of Experts (2001), Investigation of an Accidental Exposure of Radiotherapy Patients in Panama/Report of a Team of Experts, 26 May – 1 June, 2001 (PDF), Austria: International Atomic Energy Agency, Vienna, 2001.

5. Anisimov N.A., Golenkov E.A., Kharitonov D.I., “Kompozitsionnal’nyy podkhod k razrabotke parallel’nykh i raspredelennykh sistem na osnove setey Petri”, Programmirovanie, 2001, № 6, 30–43, (in Russian).

6. Denaro G. and M. Pezze`, “Petri nets and software engineering”, Lectures on Concurrency and Petri Nets, 3098, Springer-Verlag, 2004, 439–466.

7. Golenkov E.A., Sokolov A.S., “Metod avtomaticheskogo postroeniya modeli parallel’noy programmy v terminakh setey Petri”, Vychislitel’nye metody i programmirovanie, 6:2 (2005), 77–82, (in Russian).

8. Mueller Ralph et al., “Automatic Generation of Simulation Models for Semiconductor Manufacturing”, Proceedings of the 39th Conference on Winter Simulation: 40 Years! The Best is Yet to Come, WSC ’07, IEEE Press, Piscataway, NJ, USA, 2007, 648–657.

9. Desel J., “Controlling Petri Net Process Models”, Web Services and Formal Methods, 4th International Workshop, WS-FM (2007, Brisbane, Australia, September 28-29, ed. Marlon Dumas and Reiko Heckel), 2008, 17–30.

10. Laure Petrucci, “Aggregating views for Petri net model construction”, In Proc. workshop on Petri Nets and Distributed Systems (PNDS08, associated with Petri Nets 2008), 2008, 17–31.

11. Abdelghani Ghomari, Chaabane Djeraba, “Modelling Multimedia Synchronization using a Time Petri Net Based Approach”, Advances in Petri Net: Theory and Applications, eds. Tauseef Aized, Intech, 2010, http://www.intechopen.com/books/advances-in-petri-net-theory-and-applications/modeling-multimedia-synchronization-using-a-time-petri-net-based-approach-.

12. Chen Ming et al., “Petri net models for the semi-automatic construction of large scale biological networks”, Natural Computing, 10:3 (2011), 1077–1097.

13. Ballarini P. et al., “Petri Nets Compositional Modeling and Verification of Flexible Manufacturing Systems”, In 7th Annual IEEE Conference on Automation Science and Engineering (CASE 2011), 2011.

14. Alekseyev Arseniy et al., “Improved Parallel Composition of Labelled Petri Nets”, ACSD, eds. Caillaud, Benoıˆt and Carmona, Josep and Hiraishi, Kunihiko, IEEE Computer Society, 2011, 131–140.

15. Ivan Petko and Stefan Hudґak, “General composition for high level Petri nets and its properties”, Central Europ. J. Computer Science, 2:3 (2012), 222–235.

16. Durmus M. S., Yildirim U., Soylemez M. T., “Automatic Generation of Petri Net Supervisors for Railway Interlocking Design”, Control Conference (AUCC), 2012 2nd Australian, IEEE, 2012, 180–185.

17. Tarasov G.V., Kharitonov D.I, Golenkov E.A.., “Ob odnom predstavlenii funktsii v modeli imperativnoy programmy, zadannoy setyami Petri”, Modelirovanie i analiz informatsionnykh sistem, 18:2 (2011), 18–38, (in Russian).

18. Kharitonov D., Tarasov G., “Modeling function calls in program control flow in terms of Petri Nets”, ACSIJ Advances in Computer Science: an International Journal, 3:6 12 (November 2014), 82–91.

19. B. Esther Sunanda, P. Seetharamaiah, “Modeling of Safety-Critical Systems Using Petri Nets”, SIGSOFT Softw. Eng. Notes, 40:1 (2015), 1–7.

20. Kordon F. et al., “Complete Results for the 2015 Edition of the Model Checking Contest”, 2015, http://mcc.lip6.fr/2015/results.php.


Рецензия

Для цитирования:


Харитонов Д.И., Голенков Е.А., Тарасов Г.В., Леонтьев Д.В. Метод генерации примеров моделей программ в терминах сетей Петри. Моделирование и анализ информационных систем. 2015;22(4):563-577. https://doi.org/10.18255/1818-1015-2015-4-563-577

For citation:


Kharitonov D.I., Golenkov E.A., Tarasov G.V., Leontyev D.V. A Method of Sample Models of Program Construction in Terms of Petri Nets. Modeling and Analysis of Information Systems. 2015;22(4):563-577. (In Russ.) https://doi.org/10.18255/1818-1015-2015-4-563-577

Просмотров: 1146


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)