Result Details
A Rigorous Approach to Self-Reproducing Pushdown Translation
LORENC, L.; MEDUNA, A. A Rigorous Approach to Self-Reproducing Pushdown Translation. Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava: Marq software s.r.o., 2005. p. 51-58. ISBN: 80-86840-09-3.
Type
conference paper
Language
English
Authors
Lorenc Luboš, Ing., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Abstract
After a translation of an input string, x, to an output string, y, aself-reproducing pushdown transducer can make a self-reproducing stepduring which it moves y to its input tape and translates it. In thisself-reproducing way, it can repeat the translation n-times for any n>= 1. This paper demonstrates that every recursively enumerablelanguage can be characterized by the domain or the range of thetranslation obtained from a self-reproducing pushdown transducer thatrepeats its translation no more than three times.
Keywords
pushdown transducer, self-reproducing pushdown transducer, queue grammar, left-extended queue grammar, translation
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
ISBN
80-86840-09-3
Publisher
Marq software s.r.o.
Place
Ostrava
BibTeX
@inproceedings{BUT21453,
author="Luboš {Lorenc} and Alexandr {Meduna}",
title="A Rigorous Approach to Self-Reproducing Pushdown Translation",
booktitle="Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling",
year="2005",
series="1st edition",
pages="51--58",
publisher="Marq software s.r.o.",
address="Ostrava",
isbn="80-86840-09-3"
}
Projects
Optimally Integrated Models of Modern Information Technologies, GACR, Standardní projekty, GA201/04/0441, start: 2004-01-01, end: 2006-12-31, completed
Research groups
Formal Model Research Group (RG FM)
Departments