2022/10/03 by Reijo Jaakkola, Jaakkola, Reijo
Computer Science · #Advanced Algebra and Logic #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation
paper · pdf · doi:10.48550/arxiv.2210.01034
openalex publication_date 2022/10/03 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
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.