От формул вида F(t) языка LP к -ω-регулярным выражениям

• Published in: Кибернетика и системный анализ
• Date: 2020
• Main Author: Чеботарев, А.Н.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2020
• Subjects: Кібернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/190446
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: От формул вида F(t) языка LP к -ω-регулярным выражениям / А.Н. Чеботарев // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 3–17. — Бібліогр.: 5 назв. — рос.

При синтезе Σ-автомата, специфицированного в языке LP, возникает задача представления множества обратных сверхслов, задаваемых формулой F(t), в виде -ω-регулярного выражения. Построение этого выражения основано на соответствии между структурными элементами формул и -ω-регулярных выражений. Для обеспечения такого соответствия введены две дополнительные операции над -ω-регулярными множествами, соответствующие операциям квантификации в формулах. Рассмотрены методы представления этих операций в терминах языка -ω -регулярных выражений. Получены результаты, позволяющие строить -ω-регулярные выражения для достаточно широкого класса формул вида F(t) языка LP. Під час синтезу Σ-автомата, специфікованого мовою LP, виникає задача подання множини зворотних надслів, що задає формула F(t), у вигляд і -ω-регулярного виразу. Побудова цього виразу базується на відповідності між структурними елементами формул і -ω-регулярних виразів. Для забезпечення такої відповідності запроваджено дві додаткові операції над -ω-регулярними множинами, що відповідають операціям квантифікації у формулах. Розглянуто методи подання цих операцій у термінах мови -ω-регулярних виразів. Отримано результати, які дають можливість будувати відповідні -ω-регулярні вирази для достатньо широкого класу формул вигляду F(t) мови LP. In synthesis of a Σ-automaton specified in the language LP, the problem arises how to represent the set of left-infinite words defined by the formula F(t) in the form of a -ω-regular expression. Construction of this representation is based on the correspondence between structural components of formulas and -ω-regular expressions. To provide such a correspondence, two additional operations on -ω-regular sets relating to the operation of quantification in formulas are introduced. The paper focuses on the representation of these operations in terms of the -ω-regular language. The results presented in this paper allow constructing -ω-regular expressions for a wide class of LP formulas of the form F(t).