Higher-order pushdown trees are easy

Teodor Knapik, Damian Niwinski, Pawel Urzyczyn

To appear at Foundations of Software Science and Computation Structures (FOSSACS02), Grenoble, France, 6-14 April, 2002


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 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.

Server START Conference Manager
Update Time 14 Dec 2001 at 14:02:38
Maintainer fossacs02@brics.dk.
Start Conference Manager
Conference Systems