Informace o publikaci
On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops
| Název česky | O čistých multi-zásobníkových automatech, které provádí úplný zásobníkový pop |
|---|---|
| Autoři | |
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Acta Cybernetica |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Informatika |
| Klíčová slova | Pure multi-pushdown automaton, complete pushdown pop, infinite hierarchy. |
| Popis | Článek diskutuje čisté multizásobníkové automaty, které odstraňují symboly ze zásobníků pouze tak, že provedou úplný zásobníkový pop. To znamená, že během operace pop je celý obsah zásobníku porovnán s prefixem vstupu a pokud se shodují, celý obsah zásobníku je smazán a odpovídající prefix vstupu přečten. V článku je ukázáno, že tyto automaty definují nekonečnou hierarchii tříd jazyků, jenž je shodná s nekonečnou hierarchií tříd jazyků generovaných pravě lineárními prostými maticovými gramatikami. Navíc jsou diskutována některá rozšíření těchto automatů, jako např. možnost spojit dva zásobníky v jeden, či vytvoření zásobníku nového. |