The Monadic Theory of Tree-like Structures
The Monadic Theory of Tree-like Structures
复制标题
树状结构的一元理论
DOI：
10.1007/3-540-36387-4_16
复制
发表时间：
2001
影响因子：
1.2
通讯作者：
Achim Blumensath
中科院分区：
文献类型：
--
作者：
Dietmar Berwanger;Achim Blumensath
60年代末，由Buchi、Lauchli、Rabin和Shelah的工作所引发的一元二阶逻辑的研究一直受到人们的关注。MSO的吸引力是由于这样的事实，一方面，除了一阶逻辑之外，它还非常有表达力地包含了大多数模态逻辑，特别是μ演算。另一方面，MSO是足够简单的，模型检查仍然是许多结构的可判定性。因此，人们可以通过只考虑MSO来获得几个逻辑的可判定性结果。
Initiated by the work of Buchi, Lauchli, Rabin, and Shelah in the late 60s, the investigation of monadic second-order logic (MSO) has received continuous attention. The attractiveness of MSO is due to the fact that, on the one hand, it is quite expressive subsuming - besides first-order logic - most modal logics, in particular the μ-calculus. On the other hand, MSO is simple enough such that model-checking is still decidable for many structures. Hence, one can obtain decidability results for several logics by just considering MSO.