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

DOI10.1016/j.ic.2019.02.002zbMath1436.03120OpenAlexW2922221412WikidataQ128279235 ScholiaQ128279235MaRDI 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 complexitydecidabilitysatisfiabilityinterval temporal logics

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items (5)

On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning ⋮ Interval Temporal Logic for Visibly Pushdown Systems ⋮ An interval temporal logic characterization of extended \(\omega\)-regular languages ⋮ Dynamic branching in qualitative constraint-based reasoning via counting local models ⋮ Temporal Logic of Minkowski Spacetime

Cites Work

• 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
• Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
• 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

This page was built for publication: Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals