Self-reproducing pushdown transducers
Alexander Meduna; Luboš Lorenc
Kybernetika (2005)
- Volume: 41, Issue: 4, page [531]-537
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topMeduna, Alexander, and Lorenc, Luboš. "Self-reproducing pushdown transducers." Kybernetika 41.4 (2005): [531]-537. <http://eudml.org/doc/33770>.
@article{Meduna2005,
abstract = {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.},
author = {Meduna, Alexander, Lorenc, Luboš},
journal = {Kybernetika},
keywords = {pushdown transducer; self-reproducing pushdown transduction; recursively enumerable languages; pushdown transducer; self-reproducing pushdown transduction; recursively enumerable languages},
language = {eng},
number = {4},
pages = {[531]-537},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Self-reproducing pushdown transducers},
url = {http://eudml.org/doc/33770},
volume = {41},
year = {2005},
}
TY - JOUR
AU - Meduna, Alexander
AU - Lorenc, Luboš
TI - Self-reproducing pushdown transducers
JO - Kybernetika
PY - 2005
PB - Institute of Information Theory and Automation AS CR
VL - 41
IS - 4
SP - [531]
EP - 537
AB - 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.
LA - eng
KW - pushdown transducer; self-reproducing pushdown transduction; recursively enumerable languages; pushdown transducer; self-reproducing pushdown transduction; recursively enumerable languages
UR - http://eudml.org/doc/33770
ER -
References
top- Harrison M. A., Introduction to Formal Language Theory, Addison–Wesley, Reading 1978 Zbl0411.68058MR0526397
- Kleijn H. C. M., Rozenberg G., On the generative power of regular pattern grammars, Acta Inform. 20 (1983), 391–411 (1983) Zbl0541.68048MR0732313
- Meduna A., Automata and Languages: Theory and Applications, Springer, London 2000 Zbl0951.68056MR1778364
- Meduna A., 10.1080/0020716031000070616, Internat. Computer Math. 80 (2003), 679–687 Zbl1103.68587MR1984796DOI10.1080/0020716031000070616
- Meduna A., Kolar D., Regulated pushdown automata, Acta Cybernet. 14 (2000), 653–664 Zbl1011.68049MR1790232
- Revesz G. E., Introduction to Formal Languages, McGraw–Hill, New York 1983
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.