# Equality sets for recursively enumerable languages

Vesa Halava; Tero Harju; Hendrik Jan Hoogeboom^{[1]}; Michel Latteux^{[2]}

- [1] Department of Computer Science, Leiden University PO Box 9512, 2300 RA Leiden, The Netherlands;
- [2] 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 (2005)

- Volume: 39, Issue: 4, page 661-675
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHalava, Vesa, et al. "Equality sets for recursively enumerable languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.4 (2005): 661-675. <http://eudml.org/doc/246044>.

@article{Halava2005,

abstract = {We consider shifted equality sets of the form $E_G(a,g_1,g_2) = \lbrace w \mid g_1(w) = ag_2(w)\rbrace $, 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 = \pi _A(E_G(a, g_1, g_2))$ 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.},

affiliation = {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},

author = {Halava, Vesa, Harju, Tero, Hoogeboom, Hendrik Jan, Latteux, Michel},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {morphism; equality set; shifted post correspondence problem; closure properties; recursively enumerable sets; regular valence grammar; Post Correspondence Problem},

language = {eng},

number = {4},

pages = {661-675},

publisher = {EDP-Sciences},

title = {Equality sets for recursively enumerable languages},

url = {http://eudml.org/doc/246044},

volume = {39},

year = {2005},

}

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

PB - EDP-Sciences

VL - 39

IS - 4

SP - 661

EP - 675

AB - We consider shifted equality sets of the form $E_G(a,g_1,g_2) = \lbrace w \mid g_1(w) = ag_2(w)\rbrace $, 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 = \pi _A(E_G(a, g_1, g_2))$ 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.

LA - eng

KW - morphism; equality set; shifted post correspondence problem; closure properties; recursively enumerable sets; regular valence grammar; Post Correspondence Problem

UR - http://eudml.org/doc/246044

ER -

## References

top- [1] K. Culik II, A purely homomorphic characterization of recursively enumerable sets. J. Assoc. Comput. Mach. 26 (1979) 345–350. Zbl0395.68076
- [2] J. Engelfriet and G. Rozenberg, Equality languages and fixed point languages. Inform. Control 43 (1979) 20–49. Zbl0422.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. Zbl0475.68047
- [4] V. Geffert, A representation of recursively enumerable languages by two homomorphisms and a quotient. Theoret. Comput. Sci. 62 (1988) 235–249. Zbl0664.68075
- [5] S. Ginsburg, Algebraic and Automata-theoretic Properties of Formal Languages. North-Holland (1975). Zbl0325.68002MR443446
- [6] V. Halava, T. Harju, H.J. Hoogeboom and M. Latteux, Valence Languages Generated by Generalized Equality Sets. J. Autom. Lang. Comb., to appear. Zbl1083.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. Zbl1278.68134
- [8] T. Harju and J. Karhumäki, Morphisms, Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997). Zbl0866.68057MR1469999
- [9] M. Latteux and J. Leguy, On the composition of morphisms and inverse morphisms. Lect. Notes Comput. Sci. 154 (1983) 420–432. Zbl0523.68067
- [10] M. Latteux and J. Leguy, On usefulness of bifaithful rational cones. Math. Syst. Theor. 18 (1985) 19–32. Zbl0604.68083
- [11] M. Latteux and P. Turakainen, On characterization of recursively enumerable languages. Acta Informatica 28 (1990) 179–186. Zbl0686.68060
- [12] Gh. Păun, A new generative device: valence grammars. Revue Roumaine de Math. Pures et Appliquées 6 (1980) 911–924. Zbl0463.68073
- [13] A. Salomaa, Formal Languages. Academic Press, New York (1973). Zbl0262.68025MR438755
- [14] A. Salomaa, Equality sets for homomorphisms of free monoids. Acta Cybernetica 4 (1978) 127–139. Zbl0407.68077
- [15] A. Salomaa, Jewels of Formal Language Theory. Computer Science Press (1981). Zbl0487.68064MR618124
- [16] P. Turakainen, A unified approach to characterizations of recursively enumerable languages. Bulletin of the EATCS 45 (1991) 223–228. Zbl0756.68065

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.