Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером
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. The objective of this paper is to obtain a regular expression for the set difference of languages Ln...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2021
|
| Теми: | |
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/240011 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| id |
journaliasakpiua-article-240011 |
|---|---|
| record_format |
ojs |
| spelling |
journaliasakpiua-article-2400112021-09-16T11:48:22Z Set difference operation for regular Petri net languages for the producer/consumer problem with the bounded buffer Операция разности для регулярных языков сетей Петри в задаче о производителе и потребителе с ограниченным буфером Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером Statkevych, Vitalii мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression 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. The objective of this paper is to obtain a regular expression for the set difference of languages Ln \ Lm, n > m. For this purpose, we give the finite automaton which accepts the set difference of mentioned languages, and then we use the state elimination method to obtain the regular expression in the recursive form. The main result is illustrated by the examples. In an appendix, we consider the problem with two producers and two consumers with the bounded buffer of size 1. We give a reachability graph and propose the method for obtaining the regular expression. The explicit formulas are given for the problem with two producers and one consumer and also for the problem with one producer and two consumers. Рассмотрены сеть Петри в задаче о производителе и потребителе (одной из классических задач синхронизации) с ограниченным буфером размера n и регулярные формальные языки Ln, которые она порождает. Согласно цели работы — получение регулярного выражения для разности языков Ln \ Lm, n > m — построен конечный автомат, допускающий разницу указанных языков, далее методом исключения вершин получено регулярное выражение в рекурсивном виде. Основной результат проиллюстрирован на примерах. В качестве дополнения рассмотрено задачу с двумя производителями и двумя потребителями с ограниченным буфером размера 1. Построен граф достижимости и предложено конструкцию для получения регулярного выражения. В случае задачи с двумя производителями и одним потребителем, а также задачи с одним производителем и двумя потребителями указаны явные формулы. Розглянуто мережу Петрі в задачі про постачальника та споживача (одній з класичних задач синхронізації) з обмеженим буфером розміру n і регулярні формальні мови Ln, які вона породжує. Згідно з метою роботи — отримання регулярного виразу для різниці мов Ln \ Lm, n > m — побудовано скінченний автомат, який допускає різницю вказаних мов, методом вилучення вер¬шин отримано регулярний вираз в рекурсивній формі. Основний результат проілюстровано на прик¬ладах. Як доповнення розглянуто задачу з двома постачальниками та двома споживачами з об¬меженим буфером розміру 1. Побудовано граф досяжності та запропоновано конструкцію для отримання регулярного виразу. У випадку задачі з двома постачальниками та одним споживачем, а також задачі з одним постачальником та двома споживачами вказано явні формули. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2021-09-14 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/240011 10.20535/SRIT.2308-8893.2021.2.08 System research and information technologies; No. 2 (2021); 94-112 Системные исследования и информационные технологии; № 2 (2021); 94-112 Системні дослідження та інформаційні технології; № 2 (2021); 94-112 2308-8893 1681-6048 rus http://journal.iasa.kpi.ua/article/view/240011/238395 |
| institution |
System research and information technologies |
| collection |
OJS |
| language |
rus |
| topic |
мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression |
| spellingShingle |
мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression Statkevych, Vitalii Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| topic_facet |
мережа Петрі задача про постачальника та споживача мова мережі Петрі формальна мова регулярна мова скінченний автомат регулярний вираз сеть Петри задача о производителе и потребителе язык сети Петри формальный язык регулярный язык конечный автомат регулярное выражение Petri net producer/consumer problem Petri net language formal language regular language finite automaton regular expression |
| format |
Article |
| author |
Statkevych, Vitalii |
| author_facet |
Statkevych, Vitalii |
| author_sort |
Statkevych, Vitalii |
| title |
Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| title_short |
Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| title_full |
Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| title_fullStr |
Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| title_full_unstemmed |
Операція різниці для регулярних мов мереж Петрі в задачі про постачальника та споживача з обмеженим буфером |
| title_sort |
операція різниці для регулярних мов мереж петрі в задачі про постачальника та споживача з обмеженим буфером |
| title_alt |
Set difference operation for regular Petri net languages for the producer/consumer problem with the bounded buffer Операция разности для регулярных языков сетей Петри в задаче о производителе и потребителе с ограниченным буфером |
| 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. The objective of this paper is to obtain a regular expression for the set difference of languages Ln \ Lm, n > m. For this purpose, we give the finite automaton which accepts the set difference of mentioned languages, and then we use the state elimination method to obtain the regular expression in the recursive form. The main result is illustrated by the examples. In an appendix, we consider the problem with two producers and two consumers with the bounded buffer of size 1. We give a reachability graph and propose the method for obtaining the regular expression. The explicit formulas are given for the problem with two producers and one consumer and also for the problem with one producer and two consumers. |
| publisher |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| publishDate |
2021 |
| url |
http://journal.iasa.kpi.ua/article/view/240011 |
| work_keys_str_mv |
AT statkevychvitalii setdifferenceoperationforregularpetrinetlanguagesfortheproducerconsumerproblemwiththeboundedbuffer AT statkevychvitalii operaciâraznostidlâregulârnyhâzykovsetejpetrivzadačeoproizvoditeleipotrebitelesograničennymbuferom AT statkevychvitalii operacíâríznicídlâregulârnihmovmerežpetrívzadačípropostačalʹnikataspoživačazobmeženimbuferom |
| first_indexed |
2024-04-08T15:07:55Z |
| last_indexed |
2024-04-08T15:07:55Z |
| _version_ |
1795779592410103808 |