Equality sets for recursively enumerable languages

Halava, Vesa; Harju, Tero; Hoogeboom, Hendrik Jan; Latteux, Michel

doi:10.1051/ita:2005035

Geodesic

Parcourir par

Equality sets for recursively enumerable languages

Halava, Vesa ; Harju, Tero ; Hoogeboom, Hendrik Jan ¹ ; Latteux, Michel ²

¹ Department of Computer Science, Leiden University PO Box 9512, 2300 RA Leiden, The Netherlands;
² Université des Sciences et Technologies de Lille, Bâtiment M3, 59655 Villeneuve d’Ascq Cedex, France

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 4, pp. 661-675

Voir la notice de l'article provenant de la source Numdam

Résumé

We consider shifted equality sets of the form $E_{G} (a, g_{1}, g_{2}) = {w ∣ g_{1} (w) = a g_{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 \subseteq A^{*}$ is a projection of a shifted equality set, that is, $L = π_{A} (E_{G} (a, g_{1}, g_{2}))$ 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.

DOI : 10.1051/ita:2005035

Classification : 03D25, 68Q45
Keywords: morphism, equality set, shifted post correspondence problem, closure properties, recursively enumerable sets

Affiliations des auteurs :

Halava, Vesa ; Harju, Tero ; Hoogeboom, Hendrik Jan ¹ ; Latteux, Michel ²

@article{ITA_2005__39_4_661_0,
     author = {Halava, Vesa and Harju, Tero and Hoogeboom, Hendrik Jan and Latteux, Michel},
     title = {Equality sets for recursively enumerable languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {661--675},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {4},
     year = {2005},
     doi = {10.1051/ita:2005035},
     mrnumber = {2172145},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005035/}
}

TY  - JOUR
AU  - Halava, Vesa
AU  - Harju, Tero
AU  - Hoogeboom, Hendrik Jan
AU  - Latteux, Michel
TI  - Equality sets for recursively enumerable languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2005
SP  - 661
EP  - 675
VL  - 39
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005035/
DO  - 10.1051/ita:2005035
LA  - en
ID  - ITA_2005__39_4_661_0
ER  -

%0 Journal Article
%A Halava, Vesa
%A Harju, Tero
%A Hoogeboom, Hendrik Jan
%A Latteux, Michel
%T Equality sets for recursively enumerable languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 661-675
%V 39
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005035/
%R 10.1051/ita:2005035
%G en
%F ITA_2005__39_4_661_0

Halava, Vesa; Harju, Tero; Hoogeboom, Hendrik Jan; Latteux, Michel. Equality sets for recursively enumerable languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 4, pp. 661-675. doi: 10.1051/ita:2005035

Cité par Sources :