web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0001152214
Cybernetics and Systems Analysis   А - 2019 /  Issue (2020, Т. 56, № 5)
Чеботарев А. Н.
От формул вида F(t) языка LP к -ω-регулярным выражениям При синтезе <$E SIGMA>-автомата, специфицированного в языке LP, возникает задача представления множества обратных сверхслов, задаваемых формулой F(t), в виде -<$E omega>-регулярного выражения. Построение этого выражения основано на соответствии между структурными элементами формул и -<$E omega>-регулярных выражений. Для обеспечения такого соответствия введены две дополнительные операции над -<$E omega>-регулярными множествами, соответствующие операциям квантификации в формулах. Рассмотрены методы представления этих операций в терминах языка -<$E omega>-регулярных выражений. Получены результаты, позволяющие строить -<$E omega>-регулярные выражения для достаточно широкого класса формул вида F(t) языка LP.
 https://doi.org/10.1007/s10559-020-00286-x
 Scopus
Бібліографічний опис:
Чеботарев А. Н. От формул вида F(t) языка LP к -ω-регулярным выражениям. Кибернетика и системный анализ. 2020. Т. 56, № 5. С. 3–17. doi: https://doi.org/10.1007/s10559-020-00286-x URL: http://jnas.nbuv.gov.ua/article/UJRN-0001152214 |
 Cybernetics and Systems Analysis / Issue (2020, 56 (5))
Chebotarev A.N.
From LP formulas of the form F(T) to k -ω-regular expressions When synthesizing a Σ-automaton specified in the language LP, the problem arises of representing the set of left-infinite words given by a formula F(t) in the form of a –ω-regular expression. Construction of this expression is based on the correspondence between structural elements of formulas and –ω-regular expressions. To ensure this correspondence, two additional operations that correspond to the quantification operations in formulas are introduced over –ω-regular sets. Methods of representation of these operations in terms of the language of –ω-regular expressions are considered. The results obtained allow to construct –ω-regular expressions for a rather wide class of LP formulas of the form F(t). © 2020, Springer Science+Business Media, LLC, part of Springer Nature. Keywords: left-infinite word, logic LP, prefix-closed set of left-infinite words, right-bounded formula, –ω-regular expression, Pattern matching, Infinite word, Regular expressions, Regular sets, Structural elements, Computer programming languages
Cite:
Chebotarev A.N.
(2020). From LP formulas of the form F(T) to k -ω-regular expressions. Cybernetics and Systems Analysis, 56 (5), 3–17. doi: https://doi.org/10.1007/s10559-020-00286-x http://jnas.nbuv.gov.ua/article/UJRN-0001152214 [In Russian]. |
PDF