Equality sets for recursively enumerable languages

¹ Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; vesa.halava@utu.fi; harju@utu.fi
² Department of Computer Science, Leiden University PO Box 9512, 2300 RA Leiden, The Netherlands; hoogeboom@liacs.nl
³ Université des Sciences et Technologies de Lille, Bâtiment M3, 59655 Villeneuve d'Ascq Cedex, France; latteux@lifl.fr

Received: 25 February 2004
Accepted: 26 November 2004

Abstract

We consider shifted equality sets of the form E_G(a,g₁,g₂) = {ω | g₁(ω) = ag₂(ω)}, where g₁ and g₂ 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 ⊆ A* is a projection of a shifted equality set, that is, L = π_A(E_G(a,g₁,g₂)) for some (nonerasing) morphisms g₁ and g₂ 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.