УДК 519.713.1
А.М. ЧЕБОТАРЬОВ
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
ancheb@gmail.com
ПОБУДОВА ДЛЯ МНОЖИНИ — ω - СЛІВ, ЗАДАНОЇ
— ω - РЕГУЛЯРНИМ ВИРАЗОМ, ЇЇ МАКСИМАЛЬНОЇ
ПРЕФІКСНО-ЗАМКНУТОЇ ПІДМНОЖИНИ
Анотація. Наведено метод побудови для множини — ω - слів R,
заданої — ω - регулярним виразом, її максимальної префіксно-замкнутої підмножини.
Цей метод ґрунтується на побудові розміченого графу, названого графом елементарних продовжень, вершинами якого
є деякі — ω - регулярні підмножини множини R.
Кожній вершині цього графу поставлено у відповідність лінійне рівняння
над множинами — ω - слів. Отже, граф елементарних продовжень визначає систему лінійних рівнянь.
У результаті розв’язання цієї системи рівнянь для кожної вершини графу отримуємо максимальну
префіксно-замкнуту відносно R підмножину множини — ω - слів, яка відповідає цій вершині графу.
Об’єднання цих підмножин для всіх початкових вершин графу, тобто вершин,
з яких починають побудову графу, є максимальною префіксно-замкнутою підмножиною заданої множини R.
Запропоновано метод побудови такого графу, який названо методом неповних перетинів, та спосіб розв’язання системи рівнянь, яку визначає граф елементарних продовжень.
Ключові слова: — ω - слово, — ω - регулярний вираз,
префіксно-замкнута підмножина — ω - слів,
граф елементарних продовжень, лінійне рівняння над — ω - регулярними множинами.
повний текст
СПИСОК ЛІТЕРАТУРИ
- Чеботарев А.Н. Синтез -автоматов, специфицированных в логических языках LP и LF. Кибернетика и системный анализ. 2018. Т. 54, № 4. С. 16–31. URL: http://www.kibernetika.org/volumes/2018/numbers/04 .
- Thiemann P., Sulzmann M. From -regular expressions to B?chi automata via partial derivatives. In: Language and Automata Theory and Applications. LATA 2015. Dediu A.H., Formenti E., MartЗn-Vide C., Truthe B. (Eds). Lecture Notes in Computer Science. Cham: Springer, 2015. Vol. 8977. P. 287–298. https://drops.dagstuhl.de/opus/volltexte/2016.
- Чеботарьов А.М. Побудова -регулярного виразу, заданого графом елементарних продовжень. Кібернетика та системний аналіз. 2022. Т. 58, № 2. С. 3–9.
- Thomas W. Star-free regular sets of -sequences. Information and Control. 1979. Vol. 42, Iss. 2. P. 148–156.
- Diekert V., Gastin P. First-order definable languages. In: Logic and Automata: History and Perspectives. Flum J., Grdel E., Wilke T. (Eds.). Amsterdam University Press, 2007. P. 261–306.
- Pin J.-E., Perrin D. Infinite words: Automata, semigroups, logic and games. Pure and Applied Mathematics Series. Vol. 141. Amsterdam: Academic Press, 2004. 550 p.
- Chebotarev A.N. Intersection of -regular expressions. Cybernetics and Systems Analysis. Vol. 57, N 5. P. 676–684 (2021). https://doi.org/10.1007/s10559-021-00393-3.
- Calbrix H., Nivat M., Podelsky A. Ultimately periodic words of rational -languages. Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer, 1994. Vol. 802. P. 554–566.
- Angluin D., Fisman D. Learning regular omega languages. Theor. Comput. Sci. 2016. Vol. 650. P. 57–72. https://doi.org/10.1016/j.tcs.2016.07.031.
- Staiger L. On -power languages. in: New Trends in Formal Languages. Paun G., Salomaa A. (Eds.). Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer, 1997. Vol. 1218. P. 377–394. https://doi.org/10.1007/3-540-62844-4_27.
