# Equality sets for recursively enumerable languages

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

RAIRO - Theoretical Informatics and Applications (2010)

- 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 39.4 (2010): 661-675. <http://eudml.org/doc/92783>.

@article{Halava2010,

abstract = {
We consider shifted equality sets of the form EG(a,g1,g2) = \{ω | g1(ω) = ag2(ω)\}, 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 ⊆ A* is a projection
of a shifted equality set, that is, L = πA(EG(a,g1,g2)) for some (nonerasing) morphisms g1 and g2 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.
},

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

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Morphism; equality set; shifted
Post Correspondence Problem; closure properties; recursively
enumerable sets.; regular valence grammar; Post Correspondence Problem},

language = {eng},

month = {3},

number = {4},

pages = {661-675},

publisher = {EDP Sciences},

title = {Equality sets for recursively enumerable languages},

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

volume = {39},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 39

IS - 4

SP - 661

EP - 675

AB -
We consider shifted equality sets of the form EG(a,g1,g2) = {ω | g1(ω) = ag2(ω)}, 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 ⊆ A* is a projection
of a shifted equality set, that is, L = πA(EG(a,g1,g2)) for some (nonerasing) morphisms g1 and g2 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.

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/92783

ER -

## References

top- K. Culik II, A purely homomorphic characterization of recursively enumerable sets. J. Assoc. Comput. Mach.26 (1979) 345–350. Zbl0395.68076
- J. Engelfriet and G. Rozenberg, Equality languages and fixed point languages. Inform. Control43 (1979) 20–49. Zbl0422.68034
- 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
- V. Geffert, A representation of recursively enumerable languages by two homomorphisms and a quotient. Theoret. Comput. Sci.62 (1988) 235–249. Zbl0664.68075
- S. Ginsburg, Algebraic and Automata-theoretic Properties of Formal Languages. North-Holland (1975). Zbl0325.68002
- 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
- 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
- T. Harju and J. Karhumäki, Morphisms, Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997).
- M. Latteux and J. Leguy, On the composition of morphisms and inverse morphisms. Lect. Notes Comput. Sci.154 (1983) 420–432. Zbl0523.68067
- M. Latteux and J. Leguy, On usefulness of bifaithful rational cones. Math. Syst. Theor.18 (1985) 19–32. Zbl0604.68083
- M. Latteux and P. Turakainen, On characterization of recursively enumerable languages. Acta Informatica28 (1990) 179–186. Zbl0686.68060
- Gh. Păun, A new generative device: valence grammars. Revue Roumaine de Math. Pures et Appliquées6 (1980) 911–924. Zbl0463.68073
- A. Salomaa, Formal Languages. Academic Press, New York (1973). Zbl0262.68025
- A. Salomaa, Equality sets for homomorphisms of free monoids. Acta Cybernetica4 (1978) 127–139. Zbl0407.68077
- A. Salomaa, Jewels of Formal Language Theory. Computer Science Press (1981). Zbl0487.68063
- P. Turakainen, A unified approach to characterizations of recursively enumerable languages. Bulletin of the EATCS45 (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.