Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals

DOI10.1016/j.ic.2019.02.002zbMath1436.03120MaRDI QIDQ1740653

Angelo Montanari, Pietro Sala, Davide Bresolin, Guido Sciavicco, Dario Della Monica

Publication date: 2 May 2019

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11392/2403907

zbMATH Keywords

computational complexity; decidability; satisfiability; interval temporal logics

Mathematics Subject Classification ID

03B45: Modal logic (including the logic of norms)

03B25: Decidability of theories and sets of sentences

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03B44: Temporal logic

Related Items

On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• A complete classification of the expressiveness of interval logics of Allen's relations: the general and the dense cases
• Checking interval properties of computations
• Interval temporal logics over strongly discrete linear orders: expressiveness and complexity
• Intervals and tenses
• Duration calculus. A formal approach to real-time systems.
• A logical study of distributed transition systems
• The dark side of interval temporal logic: marking the undecidability border
• Expressiveness and completeness of an interval tense logic
• On the Complexity of Fragments of the Modal Logic of Allen’s Relations over Dense Structures
• The Importance of the Past in Interval Temporal Logics: The Case of Propositional Neighborhood Logic
• Decidability of the Interval Temporal Logic $\mathsf{A\bar{A}B\bar{B}}$ over the Rationals
• On the Expressiveness of the Interval Logic of Allen’s Relations Over Finite and Discrete Linear Orders
• Optimal Tableau Systems for Propositional Neighborhood Logic over All, Dense, and Discrete Linear Orders
• Tableaux for Logics of Subinterval Structures over Dense Orderings
• A decidable weakening of Compass Logic based on cone-shaped cardinal directions
• Lossy Counter Machines Decidability Cheat Sheet
• Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals
• A propositional modal logic of time intervals
• THE TEMPORAL LOGIC OF TWO DIMENSIONAL MINKOWSKI SPACETIME IS DECIDABLE
• Decidable and Undecidable Fragments of Halpern and Shoham’s Interval Temporal Logic: Towards a Complete Classification