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
+}
* 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)
* whereL
0 is a minimal linear language and is the Dyck reductiona, A. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|