论文标题
多核布尔模式逻辑的复杂性：模型检查和满意度
Complexity of Polyadic Boolean Modal Logics: Model Checking and Satisfiability
论文作者
论文摘要
我们研究了模型检查的计算复杂性和随着排列和布尔操作员在可访问性关系方面扩展的多核模态逻辑的可满足性问题的计算复杂性。首先，我们表明，模型检查问题的组合复杂性是PTIME-COMPLETE。其次，我们表明，随着可访问性关系的否定，多核模态逻辑的满足性问题是指定性的。最后，我们表明，在必要的假设下，可以使用可访问性关系的数量是由常数界限的必要假设，即访问性关系的多核模态逻辑和布尔运算符的满意度问题是指定性的。
We study the computational complexity of model checking and satisfiability problems of polyadic modal logics extended with permutations and Boolean operators on accessibility relations. First, we show that the combined complexity of the model checking problem for the resulting logic is PTime-complete. Secondly, we show that the satisfiability problem of polyadic modal logic extended with negation on accessibility relations is ExpTime-complete. Finally, we show that the satisfiability problem of polyadic modal logic with permutations and Boolean operators on accessibility relations is ExpTime-complete, under the necessary assumption that the number of accessibility relations that can be used is bounded by a constant.
