Geodesic
Self-reproducing pushdown transducers
Kybernetika, Tome 41 (2005) no. 4, pp. 531-537

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
After a translation of an input string, $x$, to an output string, $y$, a self- reproducing pushdown transducer can make a self-reproducing step during which it moves $y$ to its input tape and translates it again. In this self- reproducing way, it can repeat the translation $n$-times for any $n \ge 1$. This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than three times.
After a translation of an input string, $x$, to an output string, $y$, a self- reproducing pushdown transducer can make a self-reproducing step during which it moves $y$ to its input tape and translates it again. In this self- reproducing way, it can repeat the translation $n$-times for any $n \ge 1$. This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than three times.
Classification : 68Q45
Keywords: pushdown transducer; self-reproducing pushdown transduction; recursively enumerable languages 
Meduna, Alexander; Lorenc, Luboš. Self-reproducing pushdown transducers. Kybernetika, Tome 41 (2005) no. 4, pp. 531-537. http://geodesic.mathdoc.fr/item/KYB_2005_41_4_a6/
@article{KYB_2005_41_4_a6,
     author = {Meduna, Alexander and Lorenc, Lubo\v{s}},
     title = {Self-reproducing pushdown transducers},
     journal = {Kybernetika},
     pages = {531--537},
     year = {2005},
     volume = {41},
     number = {4},
     mrnumber = {2180361},
     zbl = {1249.68104},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2005_41_4_a6/}
}
TY  - JOUR
AU  - Meduna, Alexander
AU  - Lorenc, Luboš
TI  - Self-reproducing pushdown transducers
JO  - Kybernetika
PY  - 2005
SP  - 531
EP  - 537
VL  - 41
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/KYB_2005_41_4_a6/
LA  - en
ID  - KYB_2005_41_4_a6
ER  - 
%0 Journal Article
%A Meduna, Alexander
%A Lorenc, Luboš
%T Self-reproducing pushdown transducers
%J Kybernetika
%D 2005
%P 531-537
%V 41
%N 4
%U http://geodesic.mathdoc.fr/item/KYB_2005_41_4_a6/
%G en
%F KYB_2005_41_4_a6

[1] Harrison M. A.: Introduction to Formal Language Theory. Addison–Wesley, Reading 1978 | MR | Zbl

[2] Kleijn H. C. M., Rozenberg G.: On the generative power of regular pattern grammars. Acta Inform. 20 (1983), 391–411 | MR | Zbl

[3] Meduna A.: Automata and Languages: Theory and Applications. Springer, London 2000 | MR | Zbl

[4] Meduna A.: Simultaneously one-turn two-pushdown automata. Internat. Computer Math. 80 (2003), 679–687 | DOI | MR | Zbl

[5] Meduna A., Kolar D.: Regulated pushdown automata. Acta Cybernet. 14 (2000), 653–664 | MR | Zbl

[6] Revesz G. E.: Introduction to Formal Languages. McGraw–Hill, New York 1983