Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Two Grammatical Equivalents of Flip-Pushdown Automata
verfasst von : Peter Kostolányi
Erschienen in: SOFSEM 2015: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Flip-pushdown automata, introduced by Sarkar [7], are pushdown automata with an additional ability to reverse the contents of their pushdown, and with the most interesting setting arising when the number of such flips is limited by a constant. Two characterizations of flip-pushdown automata (with a limited number of flips) in terms of grammars are presented in this paper. First, the model is characterized by context-free grammars with an extra ability to generate reversals, which are called
reversal-generating context-free grammars
(RGCFG). Next, a model of parallel word production called
parallel interleaving grammar system
(PIGS) is introduced, for which the equivalence with flip-pushdown automata is proved, linking flip-pushdown automata to parallelism. The characterization in terms of PIGS is used to prove that flip-pushdown automata (with a limited number of flips) are weaker than ET0L systems, which solves an open problem of Holzer and Kutrib [2].