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

Abstract

top
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.

How to cite

top

Halava, 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
  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. Control43 (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.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.  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).  
  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 Informatica28 (1990) 179–186.  Zbl0686.68060
  12. Gh. Păun, A new generative device: valence grammars. Revue Roumaine de Math. Pures et Appliquées6 (1980) 911–924.  Zbl0463.68073
  13. A. Salomaa, Formal Languages. Academic Press, New York (1973).  Zbl0262.68025
  14. A. Salomaa, Equality sets for homomorphisms of free monoids. Acta Cybernetica4 (1978) 127–139.  Zbl0407.68077
  15. A. Salomaa, Jewels of Formal Language Theory. Computer Science Press (1981).  Zbl0487.68063
  16. P. Turakainen, A unified approach to characterizations of recursively enumerable languages. Bulletin of the EATCS45 (1991) 223–228.  Zbl0756.68065

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.