Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача
We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. We propose regular expressions denoting these languages in the recursive form, in case of the bounded...
Збережено в:
| Дата: | 2020 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2020
|
| Теми: | |
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/221359 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| _version_ | 1856543512841945088 |
|---|---|
| author | Statkevych, Vitalii M. |
| author_facet | Statkevych, Vitalii M. |
| author_sort | Statkevych, Vitalii M. |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2021-01-19T12:18:25Z |
| description | We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. We propose regular expressions denoting these languages in the recursive form, in case of the bounded buffer of size from 1 to 3 the explicit formulas are proposed. We transform a reachability graph into a finite automaton and use the state elimination method. We give an upper estimate for the star-height of the mentioned languages, in case of the bounded buffer of size 1 and 2 the exact values are calculated. We also consider union, intersection, Kleene closure, concatenation and set difference operations on mentioned languages. We give the finite automaton and propose regular expressions denoting the set difference of languages Ln \ L1 in the recursive form, for L2 \ L1 the explicit formula is proposed. |
| first_indexed | 2025-07-17T10:27:00Z |
| format | Article |
| id | journaliasakpiua-article-221359 |
| institution | System research and information technologies |
| language | Russian |
| last_indexed | 2025-07-17T10:27:00Z |
| publishDate | 2020 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| spelling | journaliasakpiua-article-2213592021-01-19T12:18:25Z Regular expressions for some Petri net languages for the producer/consumer problem Регулярные выражения для некоторых языков сетей Петри в задаче о производителе и потребителе Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача Statkevych, Vitalii M. Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression star-height сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение высота итерации (звездная высота) мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. We propose regular expressions denoting these languages in the recursive form, in case of the bounded buffer of size from 1 to 3 the explicit formulas are proposed. We transform a reachability graph into a finite automaton and use the state elimination method. We give an upper estimate for the star-height of the mentioned languages, in case of the bounded buffer of size 1 and 2 the exact values are calculated. We also consider union, intersection, Kleene closure, concatenation and set difference operations on mentioned languages. We give the finite automaton and propose regular expressions denoting the set difference of languages Ln \ L1 in the recursive form, for L2 \ L1 the explicit formula is proposed. Рассмотрены сеть Петри в задаче о производителе и потребителе (одной из классических задач синхронизации) с ограниченным буфером размера n и регулярные формальные языки Ln, которые она порождает. Для этих языков найдены регулярные выражения в рекурсивном виде, а в случаях ограниченного буфера размера от 1 до 3 — в виде явных формул. По графу достижимости построен конечный автомат, применен метод последовательного удаления вершин. Для высоты итерации (звездной высоты) указанных языков дана оценка сверху, а в случаях ограниченного буфера размера 1 и 2 найдены точные значения. Для указанных языков рассмотрены операции объединения, пересечения, замыкания Клини, конкатенации и разности. Для разности языков Ln \ L1 построен конечный автомат и найдены регулярные выражения в рекурсивном виде, а для разности L2 \ L1 — в виде явной формулы. Розглянуто мережу Петрі в задачі про постачальника та споживача (одній з класичних задач синхронізації) з обмеженим буфером розміру n і регулярні формальні мови Ln, які вона породжує. Для цих мов знайдено регулярні вирази в рекурсивному вигляді, а у випадках обмеженого буфера розміру від 1 до 3 — у вигляді явних формул. За графом досяжності побудовано скінченний автомат, застосовано метод послідовного видалення вершин. Для висоти ітерації (зіркової висоти) вказаних мов надано оцінку зверху, а у випадках обмеженого буфера розміру 1 та 2 знайдено точні значення. Для вказаних мов розглянуто операції об’єднання, перетину, замикання Кліні, конкатенації та різниці. Для різниці мов Ln \ L1 побудовано скінченний автомат і знайдено регулярні вирази в рекурсивному вигляді, а для різниці L2 \ L1 — у вигляді явної формули. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-12-07 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/221359 10.20535/SRIT.2308-8893.2020.3.08 System research and information technologies; No. 3 (2020); 105-123 Системные исследования и информационные технологии; № 3 (2020); 105-123 Системні дослідження та інформаційні технології; № 3 (2020); 105-123 2308-8893 1681-6048 ru http://journal.iasa.kpi.ua/article/view/221359/223560 Copyright (c) 2021 System research and information technologies |
| spellingShingle | мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) Statkevych, Vitalii M. Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_alt | Regular expressions for some Petri net languages for the producer/consumer problem Регулярные выражения для некоторых языков сетей Петри в задаче о производителе и потребителе |
| title_full | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_fullStr | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_full_unstemmed | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_short | Регулярні вирази для деяких мов мереж Петрі в задачі про постачальника та споживача |
| title_sort | регулярні вирази для деяких мов мереж петрі в задачі про постачальника та споживача |
| topic | мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) |
| topic_facet | Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression star-height сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение высота итерации (звездная высота) мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз висота ітерації (зіркова висота) |
| url | http://journal.iasa.kpi.ua/article/view/221359 |
| work_keys_str_mv | AT statkevychvitaliim regularexpressionsforsomepetrinetlanguagesfortheproducerconsumerproblem AT statkevychvitaliim regulârnyevyraženiâdlânekotoryhâzykovsetejpetrivzadačeoproizvoditeleipotrebitele AT statkevychvitaliim regulârnívirazidlâdeâkihmovmerežpetrívzadačípropostačalʹnikataspoživača |