Equality sets for recursively enumerable languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 4, pp. 661-675.

We consider shifted equality sets of the form ${E}_{G}\left(a,{g}_{1},{g}_{2}\right)=\left\{w\mid {g}_{1}\left(w\right)=a{g}_{2}\left(w\right)\right\}$, 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\left({E}_{G}\left(J\right)\right)$, where $h$ is a coding and ${E}_{G}\left(J\right)$ 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}\left({E}_{G}\left(a,{g}_{1},{g}_{2}\right)\right)$ for some (nonerasing) morphisms ${g}_{1}$ and ${g}_{2}$ 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.

DOI : https://doi.org/10.1051/ita:2005035
Classification : 03D25,  68Q45
Mots clés : morphism, equality set, shifted post correspondence problem, closure properties, recursively enumerable sets
@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
DA  - 2005///
SP  - 661
EP  - 675
VL  - 39
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2005035/
UR  - https://www.ams.org/mathscinet-getitem?mr=2172145
UR  - https://doi.org/10.1051/ita:2005035
DO  - 10.1051/ita:2005035
LA  - en
ID  - ITA_2005__39_4_661_0
ER  - 
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/

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

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

[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 0475.68047

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

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

[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 1083.68056

[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 1469999 | Zbl 0866.68057

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

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

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

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

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

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

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

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

Cité par Sources :