Decidability of the Interval Temporal Logic $mathsfAarABarB$ over the Rationals

The classification of the fragments of Halpern and Shoham’s logic with respect to decidability/undecidability of the satisfiability problem is now very close to the end. We settle one of the few remaining questions concerning the fragment ¯¯, which comprises Allen’s interval relations “meets” and “begins” and their symmetric versions. We already proved that ¯¯ is decidable over the class of all finite linear orders and undecidable over ordered domains isomorphic to ℕ. In this paper, we first show that ¯¯ is undecidable over ℝ and over the class of all Dedekind-complete linear orders. We then prove that the logic is decidable over ℚ and over the class of all linear orders.