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)

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"
}