Computational power of two stacks with restricted communication

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.

Název česky	Výpočetní síla dvou zásobníků s omezenou komunikací
Autoři	KARHUMÄKI Juhani KUNC Michal OKHOTIN Alexander
Rok publikování	2010
Druh	Článek v odborném periodiku
Časopis / Zdroj	Information and Computation
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
www	http://dx.doi.org/10.1016/j.ic.2009.07.001
Obor	Obecná matematika
Klíčová slova	Word rewriting; String rewriting; Post systems; Multi-pushdown machines; Communication; Universality
Popis	V práci jsou studovány přepisovací systémy pracující 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. Toto odvozování modeluje komunikaci dvou zásobníků podle daného protokolu určeného volbou přepisovacích pravidel. V práci jsou systematicky uvažovány různé varianty těchto systémů a je určena jejich vyjadřovací síla. Je identifikováno několik případů, kde velmi omezená komunikace překvapivě poskytuje výpočetní univerzalitu.
Související projekty:	Matematické struktury a jejich fyzikální aplikace Algebraické metody v teorii automatů a formálních jazyků II