A Rigorous Approach to Self-Reproducing Pushdown Translation
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F05%3APU55707" target="_blank" >RIV/00216305:26230/05:PU55707 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A Rigorous Approach to Self-Reproducing Pushdown Translation
Original language description
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 moore than three times.
Czech name
Rigorózní přístup k sebereprodukujícímu zásobníkovému překladu
Czech description
Po překladu vstupního řetězce x na výstupní řetězec y může sebereprodukující zásobníkový převodník provést sebereprodukující krok.Tento krok spočívá v přesunutí řetězce y na vstupní pásku. Poté jej znovu přeloží. Tímto sebereprodukujícím způsobem může překlad opakovat n-krát, pro nějaké n >= 1. V tomto článku je dokázáno, že každý rekurzivně vyčíslitelný jazyk lze přijímat i generovat sebereprodukujícím zásobníkovým převodníkem, který překlad zopakuje maximálně třikrát.
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F04%2F0441" target="_blank" >GA201/04/0441: Optimally integrated models of modern information technologies</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling
ISBN
80-86840-09-3
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
51-58
Publisher name
NEUVEDEN
Place of publication
Ostrava
Event location
Hradec nad Moravicí
Event date
Apr 19, 2005
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—