Recursive windows for grammar logics of bounded density

2025/07/20 by Olivier Gasquet, Gasquet, Olivier
Computer Science · #03B45 #68Q17 #Advanced Algebra and Logic #F.4.1 #F.4.3 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Natural Language Processing Techniques #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2507.14956

openalex publication_date 2025/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce the family of multi-modal logics of bounded density and with a tableau-like approach using finite windows which were introduced in \citeBalGasq25 and that we generalize to recursive windows. We prove that their satisfiability problem is \bfseries PSPACE-complete. As a side effect, the monomodal logic of density is shown to be in para-\bfseries PSPACE.

Citations

• Complexity of some modal logics of density (extended version)
• Decidability of Quasi-Dense Modal Logics

Related

• PSPACE-completeness of bimodal transitive weak-density logic
• Complexity of some modal logics of density (extended version)
• Shallow Models for Non-Iterative Modal Logics
• PSPACE Reasoning for Graded Modal Logics
• Recursive logic frames