On characterizations of recursively enumerable languages (Q1262786): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q1163381 |
||
Property / author | |||
Property / author: Paavo Turakainen / rank | |||
Revision as of 12:33, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On characterizations of recursively enumerable languages |
scientific article |
Statements
On characterizations of recursively enumerable languages (English)
0 references
1990
0 references
\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\).
0 references
morphism
0 references
grammar
0 references
recursively enumerable language
0 references