A decidable weakening of compass logic based on cone-shaped cardinal directions

DOI10.2168/LMCS-11(4:7)2015zbMATH Open1351.03014arXiv1510.03319OpenAlexW2260626089MaRDI QIDQ3460410FDOQ3460410

Authors: Angelo Montanari, Gabriele Puppis, Pietro Sala 

Publication date: 7 January 2016

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: We introduce a modal logic, called Cone Logic, whose formulas describe properties of points in the plane and spatial relationships between them. Points are labelled by proposition letters and spatial relations are induced by the four cone-shaped cardinal directions. Cone Logic can be seen as a weakening of Venema's Compass Logic. We prove that, unlike Compass Logic and other projection-based spatial logics, its satisfiability problem is decidable (precisely, PSPACE-complete). We also show that it is expressive enough to capture meaningful interval temporal logics - in particular, the interval temporal logic of Allen's relations "Begins", "During", and "Later", and their transposes.

Full work available at URL: https://arxiv.org/abs/1510.03319

Recommendations

• A Decidable Spatial Logic with Cone-Shaped Cardinal Directions
• Modal Logics of Topological Relations
• Undecidability of compass logic
• A modal logic for subject-oriented spatial reasoning
• Subject-oriented spatial logic

zbMATH Keywords

interval temporal logicscompass logiccone logic

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Temporal logic (03B44) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (10)

• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals
• Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
• Interval vs. point temporal logic model checking. An expressiveness comparison
• Undecidability of compass logic
• On coarser interval temporal logics
• A Logic of East and West
• Parametric interval temporal logic over infinite words
• Interval Temporal Logic for Visibly Pushdown Systems
• A Decidable Spatial Logic with Cone-Shaped Cardinal Directions

This page was built for publication: A decidable weakening of compass logic based on cone-shaped cardinal directions

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