Detail výsledku

Self-Reproducing Pushdown Transducers

LORENC, L.; MEDUNA, A. Self-Reproducing Pushdown Transducers. Kybernetika, 2005, vol. 2005, no. 4, p. 533-539. ISSN: 0023-5954.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Lorenc Luboš, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

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.

Klíčová slova

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

Rok
2005
Strany
533–539
Časopis
Kybernetika, roč. 2005, č. 4, ISSN 0023-5954
Kniha
Kybernetika
Místo
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"
}
Projekty
Optimally Integrated Models of Modern Information Technologies, GAČR, Standardní projekty, GA201/04/0441, zahájení: 2004-01-01, ukončení: 2006-12-31, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru