Equality sets for recursively enumerable languages

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

doi:10.1051/ita:2005035

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.

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
Mots-clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita:2005035/

Bibliographie
Cité par

[1] K. Culik Ii, A purely homomorphic characterization of recursively enumerable sets. J. Assoc. Comput. Mach. 26 (1979) 345-350. | Zbl

[2] J. Engelfriet and G. Rozenberg, Equality languages and fixed point languages. Inform. Control 43 (1979) 20-49. | Zbl

[3] J. Engelfriet and G. Rozenberg, Fixed point languages, equality languages, and representation of recursively enumerable languages. J. Assoc. Comput. Mach. 27 (1980) 499-518. | Zbl

[4] V. Geffert, A representation of recursively enumerable languages by two homomorphisms and a quotient. Theoret. Comput. Sci. 62 (1988) 235-249. | Zbl

[5] S. Ginsburg, Algebraic and Automata-theoretic Properties of Formal Languages. North-Holland (1975). | MR | Zbl

[6] V. Halava, T. Harju, H.J. Hoogeboom and M. Latteux, Valence Languages Generated by Generalized Equality Sets. J. Autom. Lang. Comb., to appear. | Zbl

[7] V. Halava, T. Harju, H.J. Hoogeboom and M. Latteux, Languages defined by generalized equality sets, in 14th Internat. Symp. on Fundamentals of Computation Theory, FCT'03, Malmö, Sweden, edited by A. Lingas and B.J. Nilsson. Lect. Notes Comput. Sci. 2751 (2003) 355-363.

[8] T. Harju and J. Karhumäki, Morphisms, Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997). | MR | Zbl

[9] M. Latteux and J. Leguy, On the composition of morphisms and inverse morphisms. Lect. Notes Comput. Sci. 154 (1983) 420-432. | Zbl

[10] M. Latteux and J. Leguy, On usefulness of bifaithful rational cones. Math. Syst. Theor. 18 (1985) 19-32. | Zbl

[11] M. Latteux and P. Turakainen, On characterization of recursively enumerable languages. Acta Informatica 28 (1990) 179-186. | Zbl

[12] Gh. Păun, A new generative device: valence grammars. Revue Roumaine de Math. Pures et Appliquées 6 (1980) 911-924. | Zbl

[13] A. Salomaa, Formal Languages. Academic Press, New York (1973). | MR | Zbl

[14] A. Salomaa, Equality sets for homomorphisms of free monoids. Acta Cybernetica 4 (1978) 127-139. | Zbl

[15] A. Salomaa, Jewels of Formal Language Theory. Computer Science Press (1981). | MR | Zbl

[16] P. Turakainen, A unified approach to characterizations of recursively enumerable languages. Bulletin of the EATCS 45 (1991) 223-228. | Zbl

Cité par Sources :