Informace o publikaci
On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
| Název česky | O čistých zásobníkových automatech, které provádí úplný zásobníkový pop |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek ve sborníku |
| Konference | Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings |
| Fakulta / Pracoviště MU | |
| Citace | |
| Klíčová slova | pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy |
| Popis | Článek zavádí a studuje čisté zásobníkové automaty, které vymazávají symboly ze zásobníků pouze provedením úplného zásobníkového popu. Během této operace se celý zásobník porovná s prefixem vstupního řetězce a když se shodují, tak je celý zásobník vyprázdněn a čtecí hlava se na vstupu posune za tento řetězec. Článek dokazuje, že tyto automaty definují nekonečnou hierarchii jazykových tříd. Rovněž je studován případ, kdy automat může svoje zásobníky spojovat a vytvářet nové zásobníky. |