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:	Institut Teoretické Informatiky