Publication Details
A Rigorous Approach to Self-Reproducing Pushdown Translation
LORENC Luboš and MEDUNA Alexander. A Rigorous Approach to Self-Reproducing Pushdown Translation. In: Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava, 2005, pp. 51-58. ISBN 80-86840-09-3.
Czech title
Rigorózní přístup k sebereprodukujícímu zásobníkovému překladu
Type
conference paper
Language
english
Authors
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. 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
51-58
Proceedings
Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling
Series
1st edition
Conference
8th International Conference on Information Systems Implementation and Modelling, Hradec nad Moravicí, CZ
ISBN
80-86840-09-3
Place
Ostrava, CZ
BibTeX
@INPROCEEDINGS{FITPUB7725,
author = "Lubo\v{s} Lorenc and Alexander Meduna",
title = "A Rigorous Approach to Self-Reproducing Pushdown Translation",
pages = "51--58",
booktitle = "Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling",
series = "1st edition",
year = 2005,
location = "Ostrava, CZ",
ISBN = "80-86840-09-3",
language = "english",
url = "https://www.fit.vut.cz/research/publication/7725"
}