RAIRO - Theoretical Informatics and Applications

Research Article

Equality sets for recursively enumerable languages

Vesa Halavaa1, Tero Harjua1, Hendrik Jan Hoogebooma2 and Michel Latteuxa3

a1 Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; vesa.halava@utu.fi; harju@utu.fi

a2 Department of Computer Science, Leiden University PO Box 9512, 2300 RA Leiden, The Netherlands; hoogeboom@liacs.nl

a3 Université des Sciences et Technologies de Lille, Bâtiment M3, 59655 Villeneuve d'Ascq Cedex, France; latteux@lifl.fr


We consider shifted equality sets of the form EG(a,g1,g2) = {ω | g1(ω) = ag2(ω)}, 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(EG(J)), where h is a coding and (EG(J)) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L ⊆ A* is a projection of a shifted equality set, that is, L = πA(EG(a,g1,g2)) 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.

(Received February 25 2004)

(Accepted November 26 2004)

(Online publication October 15 2005)

Key Words:

  • Morphism;
  • equality set;
  • shifted Post Correspondence Problem;
  • closure properties;
  • recursively enumerable sets.

Mathematics Subject Classification:

  • 03D25;
  • 68Q45