On characterizations of recursively enumerable languages |
| |
Authors: | Michel Latteux Paavo Turakainen |
| |
Affiliation: | (1) CNRS, UA 369, Department of Computer Science, University of Lille Flandres Artois, F-59655 Villeneuve d'Ascq, France;(2) Department of Mathematics, University of Oulu, SF-90570 Oulu, Finland |
| |
Abstract: | Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x)
–1
g(x) x in
+}![cap](/content/k64p1416mk887858/xxlarge8745.gif)
* where is an alphabet andg, 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 ofL. For instance,L = (L
0)![cap](/content/k64p1416mk887858/xxlarge8745.gif)
* whereL
0 is a minimal linear language and is the Dyck reductiona![amacr](/content/k64p1416mk887858/xxlarge257.gif) ![rarr](/content/k64p1416mk887858/xxlarge8594.gif) , A![Amacr](/content/k64p1416mk887858/xxlarge256.gif) ![rarr](/content/k64p1416mk887858/xxlarge8594.gif) . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|