Informace o publikaci
Communication of two stacks and rewriting
| Název česky | Komunikace dvou zásobníků a přepisování |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek ve sborníku |
| Konference | Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1007/11787006_40 |
| Obor | Obecná matematika |
| Klíčová slova | Multi-pushdown automaton; Word rewriting; Universal computation; Context-free language; Regular language |
| Popis | V práci se zabýváme přepisovacími systémy pracujícími 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. Tento proces je možné přirozeně chápat jako vzájemnou komunikaci dvou zásobníků podle jistého pevného protokolu. Systematicky uvažujeme různé případy těchto systémů a určujeme jejich vyjadřovací schopnost. Nalézáme několik případů, kde velmi omezená komunikace překvapivě poskytuje univerzální výpočetní sílu. |
| Související projekty: |