Why are Modal Logics so Robustly Decidable?
Why are Modal Logics so Robustly Decidable?
复制标题
为什么模态逻辑如此稳健可判定？
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
E. Grädel
中科院分区：
文献类型：
--
作者：
E. Grädel
模态逻辑广泛应用于计算机科学的许多领域，特别是硬件和软件系统的规范和验证、知识表示、数据库和人工智能。这些逻辑成功应用的最重要原因是它们在表达能力和计算复杂性之间提供了良好的平衡。在[30]中，Vardi 解决了这个问题，以确定模态逻辑的鲁棒可判定性属性的主要原因。他特别强调了树模型属性的重要性，它允许使用强大的自动机理论技术。在这里，我们根据最近对 (cid:12) 一阶逻辑和 (cid:12) 定点逻辑的保护片段的研究来讨论这个问题
Modal logics are widely used in a number of areas in computer science, in particular for the speci(cid:12)cation and veri(cid:12)cation of hardware and software systems, for knowledge representation, in databases, and in arti(cid:12)cial intelligence. The most important reason for the successful applications of these logics is that they provide a good balance between expressive power and computational complexity. In [30] Vardi adressed the question to identify the main reasons for the robust decidability properties of modal logics. In particular he stressed the importance of the tree model property, which permits the use of powerful automata-theoretic techniques. Here we discuss this question in the light of recent research on guarded fragments of (cid:12)rst-order logic and (cid:12)xed point logic