Communication of two stacks and rewriting

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00017106" target="_blank" >RIV/00216224:14330/06:00017106 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Communication of two stacks and rewriting
Original language description
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 can be naturally viewed as two stacks communicating with each other according to a fixed protocol. The paper systematically considers different cases of these systems and determines their expressiveness. Several cases are identified where very limited communication surprisingly yields universal computation power.
Czech name
Komunikace dvou zásobníků a přepisování
Czech description
V práci se zabýváme přepisovacími systémy pracujícími na slovech se středovou značkou. Odvozování se provádí umazáním prefixu nebo sufixu a následným přidáním prefixu nebo sufixu. Tento proces je možné přirozeně chápat jako vzájemnou komunikaci dvou zásobníků podle jistého pevného protokolu. Systematicky uvažujeme různé případy těchto systémů a určujeme jejich vyjadřovací schopnost. Nalézáme několik případů, kde velmi omezená komunikace překvapivě poskytuje univerzální výpočetní sílu.

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II
ISBN
978-3-540-35907-4
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Springer
Place of publication
Berlin
Event location
Venice, Italy
Event date
Jan 1, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)