А.М. ЧЕБОТАРЬОВ,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна
ancheb@gmail.com
Анотація. Під час синтезу Σ-автомата, специфікованого мовою LP, виникає задача подання множини ω-слів, що задає формула F(t), у вигляді ω-регулярного виразу. Побудова цього виразу ґрунтується на відповідності між структурними елементами формул та ω-регулярних виразів. Для забезпечення такої відповідності запроваджено дві додаткові операції над –ω-регулярними множинами, що відповідають операціям квантифікації у формулах. Задача зводилась до обчислення –ω-регулярних виразів, що визначаються цими операціями. У його основі лежить побудова графу елементарних продовжень, де певна множина нескінченних шляхів відповідає всім –ω-словам, що належать –ω-регулярній множині, яку потрібно обчислити. Запропоновано метод побудови –ω-регулярного виразу, що задається таким графом. Цей метод базується на розв’язанні системи лінійних рівнянь над –ω-регулярними множинами.
Ключові слова: –ω-слово, –ω-регулярний вираз, префіксно-замкнута множина –ω-слів, граф елементарних продовжень, лінійне рівняння над –ω-регулярними множинами.