DOI: https://doi.org/10.20535/SRIT.2308-8893.2020.3.08

Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача

Vitalii M. Statkevych

Анотація


Розглянуто мережу Петрі в задачі про постачальника та споживача (одній з класичних задач синхронізації) з обмеженим буфером розміру n і регулярні формальні мови Ln, які вона породжує. Для цих мов знайдено регулярні вирази в рекурсивному вигляді, а у випадках обмеженого буфера розміру від 1 до 3 — у вигляді явних формул. За графом досяжності побудовано скінченний автомат, застосовано метод послідовного видалення вершин. Для висоти ітерації (зіркової висоти) вказаних мов надано оцінку зверху, а у випадках обмеженого буфера розміру 1 та 2 знайдено точні значення. Для вказаних мов розглянуто операції об’єднання, перетину, замикання Кліні, конкатенації та різниці. Для різниці мов Ln \ L1 побудовано скінченний автомат і знайдено регулярні вирази в рекурсивному вигляді, а для різниці L2 \ L1 — у вигляді явної формули.

Ключові слова


мережа Петрі; задача про постачальника та споживача; мова мережі Петрі; формальна мова; регулярна мова; скінченний автомат; регулярний вираз; висота ітерації (зіркова висота)

Повний текст:

PDF (Русский)

Посилання


J. Peterson, Petri net theory and modeling of systems. Moscow: Mir, 1984.

V.E. Kotov, Petri nets. Moscow: Nauka, 1984.

T. Murata, “Petri nets: Properties, analysis and applications”, Trudy Instituta inzhenerov po elektrotekhnike i radioelektronike, vol. 77, no. 4, pp. 41–85, 1989.

A.E. Pentus and M.R. Pentus, Formal language theory. Moscow: Mekhaniko-matematicheskii fakul’tet Moskovskogo Gosudarstvenogo Universiteta, 2004.

A.E. Pentus and M.R. Pentus, The mathematical theory of formal languages. Moscow: Binom, 2006.

S. Ginsburg, The mathematical theory of context-free languages. Moscow: Mir, 1970.

J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, languages, and computation, 2nd ed. Moscow: Williams Publishing House, 2002.

V.M. Statkevych, “Regular expressions for producer/consumer Petri net languages with bounded buffer of size 1 and 2”, in 19th Int. Conf. on System Analysis and Information Technology (SAIT), Kyiv, Educational and Scientific Complex “Institute for Applied System Analysis” of National Technical University of Ukraine “Kyiv Polytechnic Institute”, 22–25 May 2017, pp. 123.

V. Statkevych, “On regular expressions for producer/consumer Petri net languages with bounded buffer”, in 4th Int. Scientific Conf. Nonlinear Analysis and Applications on memory of corresponding member of National Academy of Science of Ukraine V.S. Mel’nik, Kyiv, National Technical University of Ukraine “Kyiv Polytechnic Institute”, 4–6 Apr. 2018, pp. 68.

V. Mukhin and V. Statkevych, “On one context-free language for producer/consumer Petri net with the unbounded buffer”, in 15th Int. Conf. on Development and Application Systems (DAS), Suceava, Romania, 21–23 May 2020, pp. 137–140. doi: 10.1109/DAS49615.2020.9108948

M.Z. Zgurovsky and V.A. Denisenko, Discrete-continuous systems with controlled structure. Theory, modeling, applications. Kiev: Naukova Dumka, 1998.

A. Salomaa, Jewels of formal language theory. Moscow: Mir, 1986.

R. Valk and G. Vidal-Naquet, “Petri nets and regular languages”, Journal of Computer and System Sciences, vol. 23, issue 3, pp. 299–325, 1981.

A. Gronewold and H. Fleischhack, “Computing Petri net languages by reductions”, in 10th Int. Conf. Fundamentals of computation theory (FCT), Drezden, Germany, Springer, 22–25 Aug. 1995, pp. 253–262. doi: 10.1007/3-540-60249-6_57

S.V. Baumgertner and B.F. Melnikov, “Multi-heuristic approach for the star-height minimization of non-deterministic finite automata”, Proceedings of Voronezh State University. Series: Systems analysis and information technologies, no. 1, pp. 5–7, 2010.


Пристатейна бібліографія ГОСТ


1. Дж. Питерсон, Теория сетей Петри и моделирование систем. М.: Мир, 1984, 264 с.

2. В.Е. Котов, Сети Петри. М.: Наука. Гл. ред. физ.-мат. лит-ры, 1984, 160 с.

3. Т. Мурата, “Сети Петри: Свойства, анализ, приложения”, ТИИЭР, т. 77, № 4, с. 41–85, 1989.

4. А.Е. Пентус, и М.Р. Пентус, Теория формальных языков, М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004, 80 с.

5. А.Е. Пентус, и М.Р. Пентус, Математическая теория формальных языков. М.: "Бином", 2006, 247 с.

6. С. Гинзбург, Математическая теория контекстно-свободных языков. М.: Мир, 1970, 326 с.

7. Дж. Э. Хопкрофт, Р. Мотвани, и Дж. Д. Ульман, Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002, 528 с.

8. В.М. Статкевич, “Регулярные выражения для языков сети Петри "производитель/потребитель" с ограниченным буфером размера 1 и 2”, на Системный анализ и информационные технологии, материалы 19-й Международной научно-технической конференции SAIT 2017, Киев, 22–25 мая 2017, с. 123.

9. V. Statkevych, “On regular expressions for producer/consumer Petri net languages with bounded buffer” in Nonlinear Analysis and Applications: Materials of 4th International scientific conference on memory of corresponding member of National Academy of Science of Ukraine V.S. Mel’nik, Kyiv, 4–6 April, 2018, p. 68.

10. V. Mukhin, and V. Statkevych, “On one context-free language for producer/consumer Petri net with the unbounded buffer”, in 15th International conference on Development and Application Systems, Suceava, Romania, 21–23 May, 2020, pp. 137–140.

11. М.З. Згуровский, и В.А. Денисенко, Дискретно-непрерывные системы с управляемой структурой. Теория, моделирование, применение. К.: Наукова думка, 1998, 351 с.

12. А. Саломаа, Жемчужины теории формальных языков. М.: Мир, 1986, 159 с.

13. R. Valk, and G. Vidal-Naquet, “Petri nets and regular languages”, Journal of Computer and System Sciences, 23, pp. 299–325, 1981.

14. A. Gronewold, and H. Fleischhack, “Computing Petri net languages by reductions”, in Fundamentals of computation theory: 10th International conference; proceedings / FCT’95, Drezden, Germany, August 22–25, 1995, Springer, pp. 253–262.

15. С.В. Баумгертнер, и Б.Ф. Мельников, “Мультиэвристический подход к проблеме звездно-высотной минимизации недетерминированных конечных автоматов”, Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии, № 1, с. 5–7, 2010.