Publication Details

Self-Reproducing Translation Made by Pushdown Transducers

LORENC, L.; MEDUNA, A. Self-Reproducing Translation Made by Pushdown Transducers. PRE-PROCEEDINGS of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Faculty of Informatics MU, 2005. p. 59-67.

Czech title

Sebereprodukující překlad prováděný sebereprodukujícími zásobníkovými převodníky

Type

conference paper

Language

English

Authors

Lorenc Luboš, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)

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

59–67

Proceedings

PRE-PROCEEDINGS of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science

Publisher

Faculty of Informatics MU

Place

Brno

BibTeX

@inproceedings{BUT18055,
  author="Luboš {Lorenc} and Alexandr {Meduna}",
  title="Self-Reproducing Translation Made by Pushdown Transducers",
  booktitle="PRE-PROCEEDINGS of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  year="2005",
  pages="59--67",
  publisher="Faculty of Informatics MU",
  address="Brno"
}