The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable
The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable
复制标题
任意二级递归方案给出的一元二阶树理论是可判定的
DOI：
10.1007/11417170_5
复制
发表时间：
2005
影响因子：
3.7
通讯作者：
C. Ong
中科院分区：
文献类型：
--
作者：
Klaus Aehlig;Jolie G. de Miranda;C. Ong
一个树自动机可以模拟一个词或树自动机的成功运行，该词或树自动机工作在由一个2级二叉树表示的词或树上。特别是一元二阶理论的树木所给予的任意，而不是只有安全，递归计划的水平2是可判定的。这解决了Knapik、Niwinski和Urzyczyn提出的开放问题的第2级案例。
A tree automaton can simulate the successful runs of a word or tree automaton working on the word or tree denoted by a level-2 lambda-tree. In particular the monadic second order theory of trees given by arbitrary, rather than only by safe, recursion schemes of level 2 is decidable. This solves the level-2 case of an open problem by Knapik, Niwinski and Urzyczyn.