Equality sets for recursively enumerable languages
Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and...