Deciding monadic theories of hyperalgebraic trees
T Knapik, D Niwiński, P Urzyczyn - International Conference on Typed …, 2001 - Springer
T Knapik, D Niwiński, P Urzyczyn
International Conference on Typed Lambda Calculi and Applications, 2001•SpringerWe show that the monadic second-order theory of any infinite tree generated by a higher-
order grammar of level 2 subject to a certain syntactic restriction is decidable. By this we
extend the result of Courcelle [6] that the MSO theory of a tree generated by a grammar of
level 1 (algebraic) is decidable. To this end, we develop a technique of representing infinite
trees by infinite λ-terms, in such a way that the MSO theory of a tree can be interpreted in the
MSO theory of a λ-term.
order grammar of level 2 subject to a certain syntactic restriction is decidable. By this we
extend the result of Courcelle [6] that the MSO theory of a tree generated by a grammar of
level 1 (algebraic) is decidable. To this end, we develop a technique of representing infinite
trees by infinite λ-terms, in such a way that the MSO theory of a tree can be interpreted in the
MSO theory of a λ-term.
Abstract
We show that the monadic second-order theory of any infinite tree generated by a higher-order grammar of level 2 subject to a certain syntactic restriction is decidable. By this we extend the result of Courcelle [6] that the MSO theory of a tree generated by a grammar of level 1 (algebraic) is decidable. To this end, we develop a technique of representing infinite trees by infinite λ-terms, in such a way that the MSO theory of a tree can be interpreted in the MSO theory of a λ-term.
Springer
