
doi: 10.1007/bf01237236
\textit{V. Geffert} [Theor. Comput. Sci. 62, 235-249 (1988; Zbl 0664.68075)] has shown that each recursively enumerable language L over \(\Sigma\) can be expressed in the form \(L=\{h(x)^{-1}g(x)|\) x in \(\Delta^+\}\cap \Sigma^*\) where \(\Delta\) is an alphabet and g, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations of L. For instance, \(L=\rho (L_ 0)\cap \Sigma^*\) where \(L_ 0\) is a minimal linear language and \(\rho\) is the Dyck reduction \(a\bar a\to \epsilon\), \(A\bar A\to \epsilon\).
recursively enumerable language, grammar, Formal languages and automata, morphism
recursively enumerable language, grammar, Formal languages and automata, morphism
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
