Equality sets for recursively enumerable languages

Halava, Vesa, et al. "Equality sets for recursively enumerable languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.4 (2005): 661-675. <http://eudml.org/doc/246044>.

@article{Halava2005,
abstract = {We consider shifted equality sets of the form $E_G(a,g_1,g_2) = \lbrace w \mid g_1(w) = ag_2(w)\rbrace $, 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 \subseteq 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.},
affiliation = {Department of Computer Science, Leiden University PO Box 9512, 2300 RA Leiden, The Netherlands;; Université des Sciences et Technologies de Lille, Bâtiment M3, 59655 Villeneuve d’Ascq Cedex, France},
author = {Halava, Vesa, Harju, Tero, Hoogeboom, Hendrik Jan, Latteux, Michel},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {morphism; equality set; shifted post correspondence problem; closure properties; recursively enumerable sets; regular valence grammar; Post Correspondence Problem},
language = {eng},
number = {4},
pages = {661-675},
publisher = {EDP-Sciences},
title = {Equality sets for recursively enumerable languages},
url = {http://eudml.org/doc/246044},
volume = {39},
year = {2005},
}

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 - Informatique Théorique et Applications
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 4
SP - 661
EP - 675
AB - We consider shifted equality sets of the form $E_G(a,g_1,g_2) = \lbrace w \mid g_1(w) = ag_2(w)\rbrace $, 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 \subseteq 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.
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/246044
ER -