2006
Communication of two stacks and rewriting
KARHUMÄKI, Juhani; Michal KUNC a Alexander OKHOTINZákladní údaje
Originální název
Communication of two stacks and rewriting
Název česky
Komunikace dvou zásobníků a přepisování
Autoři
KARHUMÄKI, Juhani; Michal KUNC a Alexander OKHOTIN
Vydání
Berlin, Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, s. 468-479, 2006
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/06:00017106
Organizační jednotka
Fakulta informatiky
ISBN
3-540-35907-9
UT WoS
000239475900040
Klíčová slova anglicky
Multi-pushdown automaton; Word rewriting; Universal computation; Context-free language; Regular language
Štítky
Změněno: 24. 3. 2010 11:15, doc. Mgr. Michal Kunc, Ph.D.
V originále
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.
Česky
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.
Návaznosti
| 1M0545, projekt VaV |
|