От формул вида F(t) языка LP к -ω-регулярным выражениям
При синтезе Σ-автомата, специфицированного в языке LP, возникает задача представления множества обратных сверхслов, задаваемых формулой F(t), в виде -ω-регулярного выражения. Построение этого выражения основано на соответствии между структурными элементами формул и -ω-регулярных выражений. Для обесп...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2020 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/190446 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | От формул вида F(t) языка LP к -ω-регулярным выражениям / А.Н. Чеботарев // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 3–17. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862742184812347392 |
|---|---|
| author | Чеботарев, А.Н. |
| author_facet | Чеботарев, А.Н. |
| citation_txt | От формул вида F(t) языка LP к -ω-регулярным выражениям / А.Н. Чеботарев // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 3–17. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | При синтезе Σ-автомата, специфицированного в языке 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).
|
| first_indexed | 2025-12-07T20:24:19Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-190446 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T20:24:19Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Чеботарев, А.Н. 2023-06-08T14:57:01Z 2023-06-08T14:57:01Z 2020 От формул вида F(t) языка LP к -ω-регулярным выражениям / А.Н. Чеботарев // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 3–17. — Бібліогр.: 5 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190446 519.713.1 При синтезе Σ-автомата, специфицированного в языке 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). ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика От формул вида F(t) языка LP к -ω-регулярным выражениям Від формул вигляду F(t) мови LP до -ω-регулярних виразів From LP formulas of the form F(t) to -ω-regular expressions Article published earlier |
| spellingShingle | От формул вида F(t) языка LP к -ω-регулярным выражениям Чеботарев, А.Н. Кібернетика |
| title | От формул вида F(t) языка LP к -ω-регулярным выражениям |
| title_alt | Від формул вигляду F(t) мови LP до -ω-регулярних виразів From LP formulas of the form F(t) to -ω-regular expressions |
| title_full | От формул вида F(t) языка LP к -ω-регулярным выражениям |
| title_fullStr | От формул вида F(t) языка LP к -ω-регулярным выражениям |
| title_full_unstemmed | От формул вида F(t) языка LP к -ω-регулярным выражениям |
| title_short | От формул вида F(t) языка LP к -ω-регулярным выражениям |
| title_sort | от формул вида f(t) языка lp к -ω-регулярным выражениям |
| topic | Кібернетика |
| topic_facet | Кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190446 |
| work_keys_str_mv | AT čebotarevan otformulvidaftâzykalpkωregulârnymvyraženiâm AT čebotarevan vídformulviglâduftmovilpdoωregulârnihvirazív AT čebotarevan fromlpformulasoftheformfttoωregularexpressions |