Communication of two stacks and rewriting

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Komunikace dvou zásobníků a přepisování
Autoři

KARHUMÄKI Juhani KUNC Michal OKHOTIN Alexander

Rok publikování 2006
Druh Článek ve sborníku
Konference Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://dx.doi.org/10.1007/11787006_40
Obor Obecná matematika
Klíčová slova Multi-pushdown automaton; Word rewriting; Universal computation; Context-free language; Regular language
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.