Computational power of two stacks with restricted communication

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, 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