On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Aus International Center for Computational Logic
On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Tomáš MasopustTomáš Masopust, Alexander MedunaAlexander Meduna
Tomáš Masopust, Alexander Meduna
On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Proc. of 12th International Conference on Automata and Formal Languages (AFL), 325-336, 2008
On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Proc. of 12th International Conference on Automata and Formal Languages (AFL), 325-336, 2008
- KurzfassungAbstract
This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, the pushdown is completely emptied and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simple matrix grammars. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns. - Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@inproceedings{MM2008,
author = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
title = {On Pure Multi-Pushdown Automata that Perform Complete-Pushdown
Pops},
booktitle = {Proc. of 12th International Conference on Automata and Formal
Languages (AFL)},
year = {2008},
pages = {325-336}
}