Complexity of modal logics with Presburger constraints
From MaRDI portal
Publication:2638188
DOI10.1016/j.jal.2010.03.001zbMath1220.03008MaRDI QIDQ2638188
Stéphane P. Demri, Denis Lugiez
Publication date: 15 September 2010
Published in: Journal of Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jal.2010.03.001
computational complexity; modal logic; satisfiability; arithmetical constraint; regularity constraint
68Q25: Analysis of algorithms and problem complexity
03B45: Modal logic (including the logic of norms)
03B70: Logic in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the undecidability of logics with converse, nominals, recursion and counting
- XML schema, tree logic and sheaves automata
- General canonical models for graded normal logics. (Graded modalities. IV)
- Proof methods for modal and intuitionistic logics
- Graded modalities. I
- The covering and boundedness problems for vector addition systems
- Propositional dynamic logic of regular programs
- Decidability by filtrations for graded normal logics. (Graded modalities. V)
- Counting on CTL\(^*\): On the expressive power of monadic path logic
- A polynomial space construction of tree-like models for logics with local chains of modal connectives
- In so many possible worlds
- PSPACE Reasoning for Graded Modal Logics
- The Complexity of Poor Man's Logic
- Temporal logic can be more expressive
- Presburger Modal Logic Is PSPACE-Complete
- A first step towardsmodeling semistructured data in hybrid multimodal logic
- PDL for ordered trees
- On the complexity of integer programming
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- The Computational Complexity of Provability in Systems of Modal Propositional Logic
- A really temporal logic
- A Modal Perspective on Path Constraints
- Counting Objects
- Automated Reasoning with Analytic Tableaux and Related Methods
- Monotone AC-Tree Automata
- Logics in Artificial Intelligence
- Automata, Languages and Programming
- Term Rewriting and Applications
