Presburger Modal Logic Is PSPACE-Complete

DOI10.1007/11814771_44MaRDI QIDQ3613433zbMATH OpenOpenAlexFDO

Authors Stéphane Demri, D. Lugiez

Publication date 12 March 2009

Published in Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11814771_44

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Modal logic (including the logic of norms) (03B45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Recommendations

• Complexity of modal logics with Presburger constraints
• scientific article; zbMATH DE number 1114338
• Beyond regularity for Presburger modal logics
• scientific article; zbMATH DE number 1341607
• PSpace reasoning for graded modal logics

Cited in

(13)

• \(\mathcal{ALCQPI}_{R^+}\): rational grading in an expressive description logic with inverse and transitive roles and counting
• Complexity of modal logics with Presburger constraints
• A finite model construction for coalgebraic modal logic
• PSpace reasoning for graded modal logics
• Proof equivalence in MLL is PSPACE-complete
• PSPACE bounds for rank-1 modal logics
• Reasoning with global assumptions in arithmetic modal logics
• Coalgebraic Hybrid Logic
• scientific article; zbMATH DE number 1341607 (Why is no real title available?)
• CoLoSS: the coalgebraic logic satisfiability solver
• Beyond regularity for Presburger modal logics
• scientific article; zbMATH DE number 5046366 (Why is no real title available?)
• Coalgebraic semantics of modal logics: an overview

This page was built for publication: Presburger Modal Logic Is PSPACE-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613433)