Informace o publikaci
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 | |
| Rok publikování | 2010 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Information and Computation |
| Fakulta / Pracoviště MU | |
| 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: |