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.


closure properties, equality set, morphism, recursively enumerable sets, shifted Post Correspondence Problem



Last updated on 14/10/2025 09:52:10 AM