On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops

Č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.