Decidability of the interval temporal logic AA*BB* over the rationals
Angelo Montanari, Gabriele Puppis, Pietro Sala · 2014
Abstract. The classification of the fragments of Halpern and Shoham’s logic with respect to decidability/undecidability of the satisfiability prob-lem is now very close to the end. We settle one of the few remaining questions concerning the fragment AĀBB̄, which comprises Allen’s in-terval relations “meets ” and “begins ” and their symmetric versions. We already proved that AĀBB ̄ is decidable over the class of all finite linear orders and undecidable over ordered domains isomorphic to N. In this paper, we first show that AĀBB ̄ is undecidable over R and over the class of all Dedekind-complete linear orders. We then prove that the logic is decidable over Q and over the class of all linear orders. 1