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 (246 Finsko); Michal KUNC (203 Česká republika, garant) a Alexander OKHOTIN (643 Rusko)
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
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 |
|