2026-06-01T06:40:14Zhttps://riuma.uma.es/rest/oai/request

oai:riuma.uma.es:10630/363762026-02-03T11:23:08Zcom_10630_2254col_10630_37953

00925njm 22002777a 4500 dc Muñoz-Velasco, Emilio José author Pelegrín, Mercedes author Sala, Pletro author Sciavicco, Guido author Stan, Ionel Eduard author 2019 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. 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) https://hdl.handle.net/10630/36376 10.1016/j.artint.2018.09.001 Modalidad (Lógica) On Coarser Interval Temporal Logics