RT Journal Article
T1 On Coarser Interval Temporal Logics
A1 Muñoz-Velasco, Emilio José
A1 Pelegrín, Mercedes
A1 Sala, Pletro
A1 Sciavicco, Guido
A1 Stan, Ionel Eduard
K1 Modalidad (Lógica)
AB The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Given their generally bad computational behavior of interval temporal logics, several techniques exist to produce decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely HS3, not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen's relations are a guarantee of decidability, as we prove that the second variant, namely , remains undecidable in all interesting cases.
PB Elsevier
YR 2019
FD 2019
LK https://hdl.handle.net/10630/36376
UL https://hdl.handle.net/10630/36376
LA eng
NO Emilio Muñoz-Velasco, Mercedes Pelegrín, Pietro Sala, Guido Sciavicco, Ionel Eduard Stan, On coarser interval temporal logics, Artificial Intelligence, Volume 266, 2019, Pages 1-26, ISSN 0004-3702, https://doi.org/10.1016/j.artint.2018.09.001. (https://www.sciencedirect.com/science/article/pii/S0004370218305964)
NO TIN15-70266-C2-P-1, founded by the Spanish Ministry of Science.FPU15/05883, founded by Spanish Ministry of Education.Project Formal Methods for Verification and Synthesis of Discrete and Hybrid Systems, founded by the Italian INDAM GNCS.
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 20 ene 2026