УДК 519.713.1
ОПРЕДЕЛЕНИЕ ФИКТИВНЫХ СОСТОЯНИЙ В ∑-АВТОМАТЕ,
СИНТЕЗИРОВАННОМ ПО СПЕЦИФИКАЦИИ В ЯЗЫКЕ LP
Аннотация. Синтез детерминированного ∑-автомата, специфицированного в языке LP, состоит в последовательном выполнении двух процедур.
Первая строит автомат, имеющий подавтомат, совпадающий со специфицированным автоматом,
а вторая удаляет состояния, не принадлежащие этому подавтомату. Такие состояния называются фиктивными.
Рассмотрен способ определения фиктивных состояний. Полученные результаты позволяют соответствующий
процесс свести к нахождению так называемых основных циклов в автомате и, в конечном счете,
к проверке принадлежности периодического обратного сверхслова некоторому –ω -регулярному множеству.
Ключевые слова: ∑-автомат, фиктивное состояние, начальный сильно связный подавтомат,
нормальная форма, –ω -регулярное множество, основной цикл.
ПОЛНЫЙ ТЕКСТ
Чеботарев Анатолий Николаевич,
доктор техн. наук, ведущий научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
ancheb@gmail.com
СПИСОК ЛИТЕРАТУРЫ
- Чеботарев А.Н. Синтез ∑-автоматов, специфицированных в логических языках LP и LF. Кибернетика и системный анализ. 2018. Т. 54, № 4. С. 16–31.
- Чеботарев А.Н. Синтез процедурного представления автомата, специфицированного в логическом языке . II. Кибернетика и системный анализ. 1997. № 6. С. 115–127.
- Perrin D., Pin J.-E. Infinite words. Automata, semigroups, logic and games. Pure and applied mathematics series. Amsterdam: Elsevier, 2004. Vol. 141. 550 p.
- Bresolin D., Montanari A., Puppis G. A theory of ultimately periodic languages and automata with an application to time granularity. Acta Informatica. 2009. Vol. 46, N 5. P. 331–360.
- Чеботарев А.Н. Некоторые подмножества монадической логики первого порядка (MFO), используемые для спецификации и синтеза ∑-автоматов. Кибернетика и системный анализ. 2017. Т. 53, № 4. С. 22–36.
- Calbrix H., Nivat M., Podelsky A. Ultimately periodic words of rational ∑-languages. Lecture Notes in Computer Science. 1994. Vol. 802. P. 554–566.
- Чеботарев А.Н. Проблемы синтеза ∑-автоматов, специфицированных в языках LP и LF логики первого порядка. Кибернетика и системный анализ. 2017. Т. 53, № 5. С. 22–33.
