Deciding Monadic Theories of Hyperalgebraic Trees
Deciding Monadic Theories of Hyperalgebraic Trees
复制标题
决定超代数树的一元理论
DOI：
10.1007/3-540-45413-6_21
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
P. Urzyczyn
中科院分区：
文献类型：
--
作者：
Teodor Knapik;D. Niwinski;P. Urzyczyn
我们表明，通过这种限制，由2级的高阶语法产生的任何无限树的二阶理论是由courselle [6]确定的。由1级语法（代数）产生。 λ期的MSO理论。
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.