RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2025 Volume 32, Issue 4, Pages 213–230 (Mi da1397)

Infinite regular realizability problems

I. N. Shimanogova, M. N. Vyalyiabc

a Moscow Institute of Physics and Technology (National Research University), 1A Bld. 1 Kerchenskaya Street, 117303 Moscow, Russia
b Federal Research Center “Computer Science and Control” RAS, 44 Bld. 2 Vavilov Street, 119333 Moscow, Russia
c HSE University, 11 Pokrovsky Boulevard, 109028 Moscow, Russia

Abstract: A well-studied class of algorithmic problems is that of regular realizability, i.e. checking the non-emptiness of the intersection of a regular language with a given language. This problem has a natural algebraic interpretation which is verifying whether an element of a Boolean algebra belongs to the kernel of a certain homomorphism. This motivates the consideration of a similar problem of infinite regular realizability that is checking whether the intersection of a regular language with a given language is infinite. The paper examines the case of decidable languages and provides a comparative analysis of the complexity of infinite regular realizability problems versus regular realizability problems. Bibliogr. 22.

Keywords: regular language, regular realizability problem, arithmetic hierarchy.

UDC: 519.713

Received: 09.12.2024
Revised: 20.08.2025
Accepted: 22.09.2025

DOI: 10.33048/daio.2025.32.822



© Steklov Math. Inst. of RAS, 2026