Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
-->

УДК 519.713.1

А.М. ЧЕБОТАРЬОВ,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна
ancheb@gmail.com


ПОБУДОВА –ω-РЕГУЛЯРНОГО ВИРАЗУ,
ЗАДАНОГО ГРАФОМ ЕЛЕМЕНТАРНИХ ПРОДОВЖЕНЬ

Анотація. Під час синтезу Σ-автомата, специфікованого мовою LP, виникає задача подання множини ω-слів, що задає формула F(t), у вигляді ω-регулярного виразу. Побудова цього виразу ґрунтується на відповідності між структурними елементами формул та ω-регулярних виразів. Для забезпечення такої відповідності запроваджено дві додаткові операції над –ω-регулярними множинами, що відповідають операціям квантифікації у формулах. Задача зводилась до обчислення –ω-регулярних виразів, що визначаються цими операціями. У його основі лежить побудова графу елементарних продовжень, де певна множина нескінченних шляхів відповідає всім –ω-словам, що належать –ω-регулярній множині, яку потрібно обчислити. Запропоновано метод побудови –ω-регулярного виразу, що задається таким графом. Цей метод базується на розв’язанні системи лінійних рівнянь над –ω-регулярними множинами.

Ключові слова:ω-слово, –ω-регулярний вираз, префіксно-замкнута множина –ω-слів, граф елементарних продовжень, лінійне рівняння над –ω-регулярними множинами.


ПОВНИЙ ТЕКСТ

СПИСОК ЛІТЕРАТУРИ

  1. Чеботарев А.Н. От формул вида F(t) языка LP к –ω-регулярным выражениям. Кибернетика и системный анализ. 2020. Т. 56, № 5. С. 3–17.

  2. Thiemann P., Sulzmann M. From ω-regular expressions to Buchi automata via partial derivatives. Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer-Verlag, 2015. Vol. 8977. P. 287–298.

  3. Чеботарьов А.М. Перетин – ω-регулярних виразів. Кібернетика та системний аналіз. 2021. Т. 57, № 5. С. 12–21.

  4. Staiger L. On ω-power languages. Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer-Verlag, 1997. Vol. 1218. P. 377–394.




© 2022 Kibernetika.org. All rights reserved.