A1 Refereed original research article in a scientific journal
Equality sets for recursively enumerable languages
Authors: Halava V, Harju T, Hoogeboom HJ, Latteux M
Publisher: EDP SCIENCES S A
Publication year: 2005
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Journal acronym: RAIRO-THEOR INF APPL
Volume: 39
Issue: 4
First page : 661
Last page: 675
Number of pages: 15
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita:2005035
Abstract
We consider shifted equality sets of the form E-G(a, g(1), g(2)) = {w | g(1)( w) = ag(2)( w)}, 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 subset of 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.
We consider shifted equality sets of the form E-G(a, g(1), g(2)) = {w | g(1)( w) = ag(2)( w)}, 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 subset of 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.
Keywords:
closure properties, equality set, morphism, recursively enumerable sets, shifted Post Correspondence Problem
UTU Research Portal