Publication Details

Self-Reproducing Translation Made by Pushdown Transducers

LORENC Luboš and MEDUNA Alexander. Self-Reproducing Translation Made by Pushdown Transducers. In: PRE-PROCEEDINGS of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Faculty of Informatics MU, 2005, pp. 59-67.
Czech title
Sebereprodukující překlad prováděný sebereprodukujícími zásobníkovými převodníky
Type
conference paper
Language
english
Authors
Lorenc Luboš, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Keywords

pushdown transducer, self-reproducing pushdown transducer, queue grammar, left-extended queue grammar, translation

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 >= 1. This paper demonstrates that every recursively enumerable language can be characterized by the domain or the range of the translation obtained from a self-reproducing pushdown transducer that repeats its translation no more than three times.

Published
2005
Pages
59-67
Proceedings
PRE-PROCEEDINGS of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference
1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science -- MEMICS 2005, Znojmo, CZ
Publisher
Faculty of Informatics MU
Place
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7972,
   author = "Lubo\v{s} Lorenc and Alexander Meduna",
   title = "Self-Reproducing Translation Made by Pushdown Transducers",
   pages = "59--67",
   booktitle = "PRE-PROCEEDINGS of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
   year = 2005,
   location = "Brno, CZ",
   publisher = "Faculty of Informatics MU",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7972"
}
Back to top