Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP
Синтез детерминированного Σ-автомата, специфицированного в языке LP, состоит в последовательном выполнении двух процедур. Первая строит автомат, имеющий подавтомат, совпадающий со специфицированным автоматом, а вторая удаляет состояния, не принадлежащие этому подавтомату. Такие состояния называются...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2019 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/181029 |
| 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: | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP / А.Н. Чеботарев // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 47-57. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862546160451846144 |
|---|---|
| author | Чеботарев, А.Н. |
| author_facet | Чеботарев, А.Н. |
| citation_txt | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP / А.Н. Чеботарев // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 47-57. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Синтез детерминированного Σ-автомата, специфицированного в языке LP, состоит в последовательном выполнении двух процедур. Первая строит автомат, имеющий подавтомат, совпадающий со специфицированным автоматом, а вторая удаляет состояния, не принадлежащие этому подавтомату. Такие состояния называются фиктивными. Рассмотрен способ определения фиктивных состояний. Полученные результаты позволяют соответствующий процесс свести к нахождению так называемых основных циклов в автомате и, в конечном счете, к проверке принадлежности периодического обратного сверхслова некоторому ω-регулярному множеству.
Синтез детермінованого Σ-автомата, специфікованого мовою LP, полягає у послідовному виконанні двох процедур. Перша будує автомат, який містить у собі підавтомат, що збігається зі специфікованим автоматом, а друга видаляє стани, які не належать цьому підавтомату. Такі стани називаються фіктивними. Розглянуто спосіб визначення фіктивних станів. Отримані результати дозволяють відповідний процес звести до знаходження так званих основних циклів в автоматі і, врешті-решт, до перевірки належності періодичного зворотного надслова деякій ω-регулярній множині.
Synthesis of a deterministic Σ-automaton specified in the language LP consists in the execution of two consecutive procedures. The first one constructs the automaton that has a subautomaton, which is identical to the specified automaton, and the other deletes the states that do not belong to this subautomaton. Such states are called fictitious. The method for detecting fictitious states is considered. The obtained results allow reducing detection of fictitious states to finding so-called basic cycles and eventually to checking the membership of a periodic -word in some ω-regular set.
|
| first_indexed | 2025-11-25T10:50:37Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-181029 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-11-25T10:50:37Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Чеботарев, А.Н. 2021-10-29T17:33:44Z 2021-10-29T17:33:44Z 2019 Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP / А.Н. Чеботарев // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 47-57. — Бібліогр.: 7 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/181029 519.713.1 Синтез детерминированного Σ-автомата, специфицированного в языке LP, состоит в последовательном выполнении двух процедур. Первая строит автомат, имеющий подавтомат, совпадающий со специфицированным автоматом, а вторая удаляет состояния, не принадлежащие этому подавтомату. Такие состояния называются фиктивными. Рассмотрен способ определения фиктивных состояний. Полученные результаты позволяют соответствующий процесс свести к нахождению так называемых основных циклов в автомате и, в конечном счете, к проверке принадлежности периодического обратного сверхслова некоторому ω-регулярному множеству. Синтез детермінованого Σ-автомата, специфікованого мовою LP, полягає у послідовному виконанні двох процедур. Перша будує автомат, який містить у собі підавтомат, що збігається зі специфікованим автоматом, а друга видаляє стани, які не належать цьому підавтомату. Такі стани називаються фіктивними. Розглянуто спосіб визначення фіктивних станів. Отримані результати дозволяють відповідний процес звести до знаходження так званих основних циклів в автоматі і, врешті-решт, до перевірки належності періодичного зворотного надслова деякій ω-регулярній множині. Synthesis of a deterministic Σ-automaton specified in the language LP consists in the execution of two consecutive procedures. The first one constructs the automaton that has a subautomaton, which is identical to the specified automaton, and the other deletes the states that do not belong to this subautomaton. Such states are called fictitious. The method for detecting fictitious states is considered. The obtained results allow reducing detection of fictitious states to finding so-called basic cycles and eventually to checking the membership of a periodic -word in some ω-regular set. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP Визначення фіктивних станів в Σ-автоматі, що синтезований за специфікацією у мові LP Detecting fictitious states in Σ -automaton synthesized from the specification in the language LP Article published earlier |
| spellingShingle | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP Чеботарев, А.Н. Кібернетика |
| title | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP |
| title_alt | Визначення фіктивних станів в Σ-автоматі, що синтезований за специфікацією у мові LP Detecting fictitious states in Σ -automaton synthesized from the specification in the language LP |
| title_full | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP |
| title_fullStr | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP |
| title_full_unstemmed | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP |
| title_short | Определение фиктивных состояний в Σ-автомате, синтезированном по спецификации в языке LP |
| title_sort | определение фиктивных состояний в σ-автомате, синтезированном по спецификации в языке lp |
| topic | Кібернетика |
| topic_facet | Кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/181029 |
| work_keys_str_mv | AT čebotarevan opredeleniefiktivnyhsostoâniivσavtomatesintezirovannompospecifikaciivâzykelp AT čebotarevan viznačennâfíktivnihstanívvσavtomatíŝosintezovaniizaspecifíkacíêûumovílp AT čebotarevan detectingfictitiousstatesinσautomatonsynthesizedfromthespecificationinthelanguagelp |