Complexity of some modal logics of density (extended version)

2025/07/15 by Balbiani, Philippe, Gasquet, Olivier · 2 citations
#03B45 #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2507.11238

Abstract

By using a selective filtration argument, we prove that the satisfiability problem of the unimodal logic of density is in EXPTIME. By using a tableau-like approach, we prove that the satisfiability problem of the bimodal logic of weak density is in PSPACE.

Citations

• Decidability of Quasi-Dense Modal Logics

Cited by

• Recursive windows for grammar logics of bounded density
• PSPACE-completeness of bimodal transitive weak-density logic

Related

• On the Complexity of Elementary Modal Logics
• PSPACE-completeness of bimodal transitive weak-density logic
• Modal Logics with Hard Diamond-free Fragments
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
• Complexity Results for Modal Dependence Logic