zbMATH — the first resource for mathematics

Higher-order pushdown trees are easy. (English) Zbl 1077.03508
Nielsen, Mogens (ed.) et al., Foundations of software science and computation structures. 5th international conference, FOSSACS 2002, held as part of the joint European conferences on theory and practice of software, ETAPS 2002, Grenoble, France, April 8–12, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43366-X). Lect. Notes Comput. Sci. 2303, 205-222 (2002).
Summary: We show that the monadic second-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 (pushdown of level 1) trees and our own result on trees of level 2.
For the entire collection see [Zbl 0989.00051].

03B25 Decidability of theories and sets of sentences
03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
Full Text: Link