Complexity of modal logics with Presburger constraints
From MaRDI portal
Publication:2638188
DOI10.1016/j.jal.2010.03.001zbMath1220.03008MaRDI QIDQ2638188
Denis Lugiez, Stéphane P. Demri
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.)
Related Items
On regular paths with counting and data tests, Reasoning with Global Assumptions in Arithmetic Modal Logics
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