Complexity results for modal logic with recursion via translations and tableaux
Open Access
- 7 August 2024
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is
Abstract
This paper studies the complexity of classical modal logics and of their extension with fixed-point operators, using translations to transfer results across logics. In particular, we show several complexity results for multi-agent logics via translations to and from the $\mu$-calculus and modal logic, which allow us to transfer known upper and lower bounds. We also use these translations to introduce terminating and non-terminating tableau systems for the logics we study, based on Kozen's tableau for the $\mu$-calculus and the one of Fitting and Massacci for modal logic. Finally, we describe these tableaux with $\mu$-calculus formulas, thus reducing the satisfiability of each of these logics to the satisfiability of the $\mu$-calculus, resulting in a general 2EXP upper bound for satisfiability testing.Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- The complexity of identifying characteristic formulaeJournal of Logical and Algebraic Methods in Programming, 2020
- The μ-Calculus Alternation Depth Hierarchy is infinite over finite planar graphsTheoretical Computer Science, 2018
- The mu-calculus and Model Checking2018
- Handbook of Model Checking2018
- On the -calculus over transitive and finite transitive framesTheoretical Computer Science, 2010
- Strongly analytic tableaux for normal modal logics1994
- A guide to completeness and complexity for modal logics of knowledge and beliefArtificial Intelligence, 1992
- Results on the propositional μ-calculusTheoretical Computer Science, 1983
- Propositional dynamic logic of regular programsJournal of Computer and System Sciences, 1979
- ber das Problem der WohlordnungMathematische Annalen, 1915