spacer
EDP Sciences Journals List
Home arrow Document
Subscriber Authentication Point
   
Issue Theoret. Informatics Appl.
Volume 39, Number 4, October-December 2005
Page(s) 661 - 675
DOI 10.1051/ita:2005035

Theoret. Informatics Appl. 39, 661-675 (2005)
DOI: 10.1051/ita:2005035

Equality sets for recursively enumerable languages

Vesa Halava1, Tero Harju1, Hendrik Jan Hoogeboom2 and Michel Latteux3

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


(Received February 25, 2004. Accepted November 26, 2004.)

Abstract
We consider shifted equality sets of the form $E_G(a,g_1,g_2) = \{ w \mid g_1(w) = ag_2(w)\}$, where g1 and g2 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 \subseteq 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 g1 and g2 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 Subject Classification. 03D25, 68Q45.

Key words: Morphism -- equality set -- shifted Post Correspondence Problem -- closure properties -- recursively enumerable sets.


© EDP Sciences 2005


What is OpenURL?