RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2026 Volume 67, Number 5, Pages 1007–1019 (Mi smj8073)

Computable isomorphisms of relative regular Boolean algebras

I. N. Shimanogova, M. N. Vyalyiabc

a Moscow Institute of Physics and Technology (National Research University), Moscow, Russia
b Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Moscow, Russia
c HSE University, Moscow, Russia

Abstract: We consider a class of Boolean algebras formed by intersections of regular languages with a given language. In the case where such an algebra is isomorphic to the algebra of regular languages, we prove the existence of an isomorphism that is computable using oracles for the regular realizability problem and the infinite regular realizability problem. This result yields the existence of a computable isomorphism between the Boolean algebras of regular languages over one-letter and two-letter alphabets. We also obtain a lower bound on the complexity of this problem.

Keywords: regular realizability problems, Boolean algebras, relative regular algebras, computational complexity, regular languages.

UDC: 519.713.2+512.563

MSC: 35R30

Received: 10.12.2025
Revised: 18.06.2026
Accepted: 24.06.2026

DOI: 10.33048/smzh.2026.67.519


 English version:
Siberian Mathematical Journal, 2026, 67:5, 1203–1212


© Steklov Math. Inst. of RAS, 2026