Computable Isomorphisms of Relative Regular Boolean Algebras
I. N. Shimanogov, M. Vyalyi · Siberian Mathematical Journal · 2026
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.