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
topHow 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.
- J. Engelfriet and G. Rozenberg, Equality languages and fixed point languages. Inform. Control43 (1979) 20–49.
- J. Engelfriet and G. Rozenberg, Fixed point languages, equality languages, and representation of recursively enumerable languages. J. Assoc. Comput. Mach.27 (1980) 499–518.
- V. Geffert, A representation of recursively enumerable languages by two homomorphisms and a quotient. Theoret. Comput. Sci.62 (1988) 235–249.
- S. Ginsburg, Algebraic and Automata-theoretic Properties of Formal Languages. North-Holland (1975).
- V. Halava, T. Harju, H.J. Hoogeboom and M. Latteux, Valence Languages Generated by Generalized Equality Sets. J. Autom. Lang. Comb., to appear.
- 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.
- 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.
- M. Latteux and J. Leguy, On usefulness of bifaithful rational cones. Math. Syst. Theor.18 (1985) 19–32.
- M. Latteux and P. Turakainen, On characterization of recursively enumerable languages. Acta Informatica28 (1990) 179–186.
- Gh. Păun, A new generative device: valence grammars. Revue Roumaine de Math. Pures et Appliquées6 (1980) 911–924.
- A. Salomaa, Formal Languages. Academic Press, New York (1973).
- A. Salomaa, Equality sets for homomorphisms of free monoids. Acta Cybernetica4 (1978) 127–139.
- A. Salomaa, Jewels of Formal Language Theory. Computer Science Press (1981).
- P. Turakainen, A unified approach to characterizations of recursively enumerable languages. Bulletin of the EATCS45 (1991) 223–228.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.