КіСА | Зміст

Том 60 >>> № 6 ЛИСТОПАД — ГРУДЕНЬ 2024

-->

УДК 519.713.1

А.М. ЧЕБОТАРЬОВ
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
ancheb@gmail.com

ДОПОВНЕННЯ –ω-РЕГУЛЯРНИХ ВИРАЗІВ. І

Анотація. Під час використання ω-регулярних виразів у задачах верифікації та синтезу реактивних систем виникає проблема доповнення цих виразів, яка пов’язана з перевіркою включення ω-регулярних мов. Для цього зазвичай ω-регулярну мову задають ω-автоматом A і будують автомат, що розпізнає доповнення ω-регулярної мови, заданої автоматом A. У статті замість ω-регулярних виразів розглянуто симетричні –ω-регулярні вирази, пов’язані з поняттям зворотного слова (ω-слова). Перехід від алгоритму доповнення –ω-регулярного виразу до відповідного алгоритму для ω-регулярного виразу полягає в заміні використаних понять симетричними поняттями. Розглянуто задачу безпосереднього переходу від –ω-регулярного виразу, що задає –ω-мову, до –ω-регулярного виразу, який задає доповнення цієї мови. Серед ω-регулярних виразів виокремлено три класи, для кожного з яких визначено алгоритм побудови доповнення –ω-регулярного виразу із цього класу. Це суттєво спрощує розв’язання розглядуваної задачі. Розглянуто клас виразів вигляду ∑^–ωR, де R ∈∑^* і не має вигляду R₁∑^*.

Ключові слова: –ω-регулярний вираз, доповнення –ω-регулярного виразу, суфікс регулярного виразу, алфавіт ∑^′, сумісні слова, умова сумісності.

повний текст

СПИСОК ЛІТЕРАТУРИ

1. Kupferman O., Vardi M. Complementation constructions for nondeterministic automata on infinite words. Proc. TACAS’05. Lecture Notes Comput. Sci. 2005. Vol. 3440. P. 206–211. URL: https://doi.org/10.1007/ 978-3-540-31980-1_14 .

2. Fogarty S., Kupferman O., Vardi M., Wilke T. Unifying B?chi ñomplementation ñonstructions. Logical Methods in Computer Science. 2011. Vol. 9, N 1. P. 248–263. URL: https://doi.org/10.2168/LMCS-9(1:13)2013 .

3. Vardi M.Y., Fogarty S., Yong Li, Yih-Kuen Tsay. Towards a grand unification of Bchi ñomplementation ñonstructions. In: Principles of Systems Design. LNCS. 2022. Vol. 13660. P. 185–207. URL: https://doi.org/10.1007/978-3-031-22337-2_9 .

4. Chebotarev A.N. Synthesis of -automata specified in the first order logical languages LP and LF. Cybernetics and Systems Analysis. 2018. Vol. 54, N 4. P. 527–540. URL: https://doi.org/10.1007/ s10559-018-0054-8 .

5. Chebotarev A.N. Detecting fictitious states in a -automaton synthesized from the specification in the language LP. Cybernetics and Systems Analysis. 2019. Vol. 55, N 5. P. 742–751. URL: https://doi.org/10.1007/s10559-019-00184-x .

6. Diekert V., Gastin P. First-order definable languages. In: Logic and Automata: History and Perspectives. Flum J., Grdel E., Wilke T. (Eds.). Amsterdam University Press, 2007. P. 261–306.

7. Pin J.-E., Perrin D. Infinite words: Automata, semigroups, logic and games. Pure and Applied Mathematics Series. Vol. 141. Amsterdam: Academic Press, 2004. 550 p.

8. Чеботарьов А.М. Перетин – ω-регулярних виразів. Кібернетика та системний аналіз. 2021. Т. 57, № 5. С. 12–21.