Publication Details

Self-Reproducing Pushdown Transducers

LORENC Luboš and MEDUNA Alexander. Self-Reproducing Pushdown Transducers. Kybernetika, vol. 2005, no. 4, pp. 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. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)

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, CZ

BibTeX

@ARTICLE{FITPUB7872,
   author = "Lubo\v{s} Lorenc and Alexander Meduna",
   title = "Self-Reproducing Pushdown Transducers",
   pages = "533--539",
   booktitle = "Kybernetika",
   journal = "Kybernetika",
   volume = 2005,
   number = 4,
   year = 2005,
   location = "Praha, CZ",
   ISSN = "0023-5954",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7872"
}