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.