Publication result detail

Self-Reproducing Pushdown Transducers

LORENC, L.; MEDUNA, A.

Original Title

Self-Reproducing Pushdown Transducers

English Title

Self-Reproducing Pushdown Transducers

Type

Peer-reviewed article not indexed in WoS or Scopus

Original Abstract

After a translation of an input string, x, to an output string, y, aself-reproducing pushdown transducer can make a self-reproducing stepduring which it moves y to its input tape and translates it again. Inthis self-reproducing way, it can repeat the translation n-times forany n >= 1. This paper demonstrates that every recursivelyenumerable language can be characterized by the domain of thetranslation obtained from a self-reproducing pushdown transducer thatrepeats its translation no more than three times.

English abstract

After a translation of an input string, x, to an output string, y, aself-reproducing pushdown transducer can make a self-reproducing stepduring which it moves y to its input tape and translates it again. Inthis self-reproducing way, it can repeat the translation n-times forany n >= 1. This paper demonstrates that every recursivelyenumerable language can be characterized by the domain of thetranslation obtained from a self-reproducing pushdown transducer thatrepeats its translation no more than three times.

Keywords

pushdown transducer, self-reproducing pushdown transduction, recursively enumerable languages

Key words in English

pushdown transducer, self-reproducing pushdown transduction, recursively enumerable languages

Authors

LORENC, L.; MEDUNA, A.

Released

13.09.2005

Location

Praha

Book

Kybernetika

ISBN

0023-5954

Periodical

KYBERNETIKA

Volume

2005

Number

4

State

Czech Republic

Pages from

533

Pages to

539

Pages count

7

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