Equality sets for recursively enumerable languages

: Halava V, Harju T, Hoogeboom HJ, Latteux M

Publisher: EDP SCIENCES S A

: 2005

: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS

: RAIRO-THEOR INF APPL

: 39

: 4

: 661

: 675

: 15

: 0988-3754

DOI: https://doi.org/10.1051/ita:2005035

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.

Mathematics