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.
翻译：我们研究了模型检查的复杂性和多式模式逻辑的可比较性问题,这些逻辑在无障碍关系上与变异者和布尔恩操作者一起延伸。首先,我们表明,模型检查问题在由此形成的逻辑上的综合复杂性是PTime-complete。第二,我们表明,多式模式逻辑在否定无障碍关系的同时延伸的可比较性问题是ExpTime-complete。最后,我们表明,与变异者和布尔恩操作者在无障碍关系上的多式逻辑的可比较性问题是耗尽时间的,其必要的假设是,可以使用的无障碍关系的数量与常数相联。
相关内容
微信扫码咨询专知VIP会员