Publication result detail

Self-Reproducing Pushdown Transducers

LORENC, L.; MEDUNA, A.

Original Title

Self-Reproducing Pushdown Transducers

English Title

Self-Reproducing Pushdown Transducers

Type

Paper in proceedings outside WoS and Scopus

Original 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 of the translation obtained from a self-reproducing pushdown transducer that repeats its translation no more than three times.

English 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 of the translation obtained from a self-reproducing pushdown transducer that repeats its translation no more than three times.

Keywords

pushdown transducer, self-reproducing pushdown transducer, queue grammar, left-extended queue grammar, translation

Key words in English

pushdown transducer, self-reproducing pushdown transducer, queue grammar, left-extended queue grammar, translation

Authors

LORENC, L.; MEDUNA, A.

Released

12.05.2004

Publisher

Marq software s.r.o.

Location

Ostrava

ISBN

80-85988-99-2

Book

Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling

Edition

1st edition

Pages from

155

Pages to

160

Pages count

6

BibTex

@inproceedings{BUT17117,
  author="Luboš {Lorenc} and Alexandr {Meduna}",
  title="Self-Reproducing Pushdown Transducers",
  booktitle="Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling",
  year="2004",
  series="1st edition",
  pages="155--160",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-85988-99-2"
}