Computational power of two stacks with restricted communication

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F10%3A00042811" target="_blank" >RIV/00216224:14310/10:00042811 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Computational power of two stacks with restricted communication
Popis výsledku v původním jazyce
Rewriting systems working on words with a center marker are considered. The derivation is done by erasing a prefix or a suffix and then adding a prefix or a suffix. This models a communication of two stacks according to a fixed protocol defined by the choice of rewriting rules. The paper systematically considers different cases of these systems and determines their expressive power. Several cases are identified where very restricted communication surprisingly yields computational universality.
Název v anglickém jazyce
Computational power of two stacks with restricted communication
Popis výsledku anglicky
Rewriting systems working on words with a center marker are considered. The derivation is done by erasing a prefix or a suffix and then adding a prefix or a suffix. This models a communication of two stacks according to a fixed protocol defined by the choice of rewriting rules. The paper systematically considers different cases of these systems and determines their expressive power. Several cases are identified where very restricted communication surprisingly yields computational universality.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—

Projekt
<a href="/cs/project/GA201%2F09%2F1313" target="_blank" >GA201/09/1313: Algebraické metody v teorii automatů a formálních jazyků II</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2010
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)