PSPACE-completeness of bimodal transitive weak-density logic

2025/07/20 by Philippe Balbiani, Balbiani, Philippe, Olivier Gasquet +1
Computer Science · Arts and Humanities · #Logic, Reasoning, and Knowledge #Syntax, Semantics, Linguistic Variation #Constraint Satisfaction and Optimization

paper · pdf · doi:10.48550/arxiv.2507.14949

Abstract

International audience

Citations

• Complexity of some modal logics of density (extended version)
• Reopening of the conjecture about the decidability of Quasi-Dense Modal Logics (Comments on Lyon & Ostropolski-Nalewaja's result)
• Decidability of Quasi-Dense Modal Logics

Related

• Complexity of some modal logics of density (extended version)
• Recursive windows for grammar logics of bounded density
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
• PH = PSPACE
• EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of Subset Spaces, Part 2: EXPSPACE-Hardness