Publication Details

A Rigorous Approach to Self-Reproducing Pushdown Translation

LORENC, L., MEDUNA, A. A Rigorous Approach to Self-Reproducing Pushdown Translation. In Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava: 2005. p. 51-58. ISBN: 80-86840-09-3.

Czech title

Rigorózní přístup k sebereprodukujícímu zásobníkovému překladu

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

51–58

Proceedings

Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling

Series

1st edition

ISBN

80-86840-09-3

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",
  address="Ostrava",
  isbn="80-86840-09-3"
}