Computational power of two stacks with restricted communication

Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, 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:

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

Další info