1/2014 - Decidability of the interval temporal logic AA ̄BB ̄ over the rationals
Angelo Montanari, Gabriele Puppis, and Pietro Sala
| Titolo | Decidability of the interval temporal logic AA ̄BB ̄ over the rationals |
|---|---|
| Numero | 1/2014 |
| Sottomesso da | Angelo Montanari |
| Sottomesso il | 12/6/2014 |
| Stato | Draft |
| Autori | Angelo Montanari, Gabriele Puppis, and Pietro Sala |
| Abstract | 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 AA ̄BB ̄, which comprises Allen's interval relations "meets'' and "begins'' and their symmetric versions. We already proved that AA ̄BB ̄ is decidable over the class of all finite linear orders and undecidable over ordered domains isomorphic to the natural numbers. In this paper, we first show that AA ̄BB ̄ is undecidable over the real numbers and over the class of all Dedekind-complete linear orders. We then prove that the logic is decidable over the rational numbers and over the class of all linear orders. |
| File | 1-2014-montanari.pdf |