УДК 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.
