Advanced Search

We consider shifted equality sets of the form $E_G(a,g_1,g_2)=\{w\mid g_1\left(w\right)=a{g}_2\left(w\right)\}$, 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\left(E_G\left(J\right)\right)$, where $h$ is a coding and $E_G\left(J\right)$ 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\left(E_G(a,g_1,g_2)\right)$ 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...

We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter...