Publication Details
Self-Reproducing Pushdown Transducers
LORENC, L., MEDUNA, A. Self-Reproducing Pushdown Transducers. Kybernetika, 2005, vol. 2005, no. 4, p. 533-539. ISSN: 0023-5954.
Czech title
Sebereprodukující zásobníkové převodníky
Type
journal article
Language
English
Authors
Lorenc Luboš, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Keywords
pushdown transducer, self-reproducing pushdown transduction, recursively enumerable languages
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 of the translation obtained from a self-reproducing pushdown transducer that repeats its translation no more than three times.
Published
2005
Pages
533–539
Journal
Kybernetika, vol. 2005, no. 4, ISSN 0023-5954
Book
Kybernetika
Place
Praha
BibTeX
@article{BUT42911,
author="Luboš {Lorenc} and Alexandr {Meduna}",
title="Self-Reproducing Pushdown Transducers",
journal="Kybernetika",
year="2005",
volume="2005",
number="4",
pages="533--539",
issn="0023-5954"
}