On Coarser Interval Temporal Logics and their Satisfiability Problem

The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Their computational behaviour is generally bad, and several restrictions have been considered in order to define 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). We prove that one of them (denoted here by HS7) is still generally undecidable, while the other one (HS3) becomes, perhaps surprisingly, PSpace-complete, at least in the finite