Equality sets for recursively enumerable languages
We consider shifted equality sets of the form E-G(a, g(1), g(2)) = {w | g(1)( w) = ag(2)( w)}, where g(1) and g(2) are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(E-G( J)), where h is a coding and E-G(J) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L subset of A* is a projection of a shifted equality set, that is, L = pi(A)(E-G(a, g(1), g(2))) for some ( nonerasing) morphisms g(1) and g(2) and a letter a, where pi(A) deletes the letters not in A. Then we deduce that recursively enumerable star languages coincide with the projections of equality sets.
equality set morphism closure properties shifted post correspondence problem recursively enumerable sets