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 is contained in A~* is a projection of a shifted equality set, that is, L = π_A (E_G(a, g_1, g_2)) for some (nonerasing) morphisms g_1 and g_2 and a letter a, where π_A deletes the letters not in A. Then we deduce that recursively enumerable star languages coincide with the projections of equality sets.