Anzeige
Erschienen in:
2002 | OriginalPaper | Buchkapitel
Higher-Order Pushdown Trees Are Easy
verfasst von : Teodor Knapik, Damian Niwiński, Paweł Urzyczyn
Erschienen in: Foundations of Software Science and Computation Structures
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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
We show that the monadicsec ond-order theory of an infinite tree recognized by a higher-order pushdown automaton of any level is decidable. We also show that trees recognized by pushdown automata of level n coincide with trees generated by safe higher-order grammars of level n. Our decidability result extends the result of Courcelle on algebraic(pushdo wn of level 1) trees and our own result on trees of level 2.