Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-19T06:45:42.533Z Has data issue: false hasContentIssue false
  • English
  • Français

Equality sets for recursively enumerable languages

Published online by Cambridge University Press:  15 October 2005

Vesa Halava ,
Tero Harju ,
Hendrik Jan Hoogeboom  and
Michel Latteux
Vesa Halava
Affiliation:
Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; [email protected]; [email protected]
Tero Harju
Affiliation:
Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; [email protected]; [email protected]
Hendrik Jan Hoogeboom
Affiliation:
Department of Computer Science, Leiden University PO Box 9512, 2300 RA Leiden, The Netherlands; [email protected]
Michel Latteux
Affiliation:
Université des Sciences et Technologies de Lille, Bâtiment M3, 59655 Villeneuve d'Ascq Cedex, France; [email protected]
Get access

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.

Keywords

Morphismequality setshifted Post Correspondence Problemclosure propertiesrecursively enumerable sets.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 4 , October 2005 , pp. 661 - 675
Copyright
© EDP Sciences, 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Culik II, K., A purely homomorphic characterization of recursively enumerable sets. J. Assoc. Comput. Mach. 26 (1979) 345–350. CrossRef
Engelfriet, J. and Rozenberg, G., Equality languages and fixed point languages. Inform. Control 43 (1979) 20–49. CrossRef
Engelfriet, J. and Rozenberg, G., Fixed point languages, equality languages, and representation of recursively enumerable languages. J. Assoc. Comput. Mach. 27 (1980) 499–518. CrossRef
Geffert, V., A representation of recursively enumerable languages by two homomorphisms and a quotient. Theoret. Comput. Sci. 62 (1988) 235–249. CrossRef
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.
Halava, V., Harju, T., Hoogeboom, H.J. and Latteux, M., 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. CrossRef
T. Harju and J. Karhumäki, Morphisms, Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997).
Latteux, M. and Leguy, J., On the composition of morphisms and inverse morphisms. Lect. Notes Comput. Sci. 154 (1983) 420–432. CrossRef
Latteux, M. and Leguy, J., On usefulness of bifaithful rational cones. Math. Syst. Theor. 18 (1985) 19–32. CrossRef
Latteux, M. and Turakainen, P., On characterization of recursively enumerable languages. Acta Informatica 28 (1990) 179–186. CrossRef
Păun, Gh., A new generative device: valence grammars. Revue Roumaine de Math. Pures et Appliquées 6 (1980) 911–924.
A. Salomaa, Formal Languages. Academic Press, New York (1973).
Salomaa, A., Equality sets for homomorphisms of free monoids. Acta Cybernetica 4 (1978) 127–139.
A. Salomaa, Jewels of Formal Language Theory. Computer Science Press (1981).
Turakainen, P., A unified approach to characterizations of recursively enumerable languages. Bulletin of the EATCS 45 (1991) 223–228.