Computational power of two stacks with restricted communication

Název česky Výpočetní síla dvou zásobníků s omezenou komunikací
Autoři

KARHUMÄKI Juhani KUNC Michal OKHOTIN Alexander

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.