Interval temporal logics (ITLs) are logics for reasoning about temporal statements expressed over intervals, i.e., periods of time. The most famous temporal logic for intervals studied so far is probably Halpern and Shoham’s HS, which is the logic of the thirteen Allen’s interval relations. Unfortunately, HS and most of its fragments are undecidable. This discouraged the research in this area until recently, when a number non-trivial decidable ITLs have been discovered. This paper is a contribution towards the complete classification of all different fragments of HS. We consider here different combinations of the interval relations begins (B), meets (A), later (L) and their inverses A, B and L. We know from previous work that the combination ABBA is decidable only when finite domains are considered (and undecidable elsewhere), and that ABB is decidable over the natural numbers. In the present paper we show that, over strongly discrete linear models (e.g. finite orders, the naturals, the integers), decidability of ABB can be further extended to capture the language ABBL, which lies strictly in between ABB and ABBA. The logic ABBL turns out to be maximal w.r.t decidability over the considered classes, and its satisfiability problem is EXPSPACE-complete. In this paper we also provide an optimal non-deterministic decision procedure, and we show that the language is powerful enough to polynomially encode metric constraints on the length of the current interval.
On Begin, Meets and Before
BRESOLIN, Davide;SALA, Pietro;
2012-01-01
Abstract
Interval temporal logics (ITLs) are logics for reasoning about temporal statements expressed over intervals, i.e., periods of time. The most famous temporal logic for intervals studied so far is probably Halpern and Shoham’s HS, which is the logic of the thirteen Allen’s interval relations. Unfortunately, HS and most of its fragments are undecidable. This discouraged the research in this area until recently, when a number non-trivial decidable ITLs have been discovered. This paper is a contribution towards the complete classification of all different fragments of HS. We consider here different combinations of the interval relations begins (B), meets (A), later (L) and their inverses A, B and L. We know from previous work that the combination ABBA is decidable only when finite domains are considered (and undecidable elsewhere), and that ABB is decidable over the natural numbers. In the present paper we show that, over strongly discrete linear models (e.g. finite orders, the naturals, the integers), decidability of ABB can be further extended to capture the language ABBL, which lies strictly in between ABB and ABBA. The logic ABBL turns out to be maximal w.r.t decidability over the considered classes, and its satisfiability problem is EXPSPACE-complete. In this paper we also provide an optimal non-deterministic decision procedure, and we show that the language is powerful enough to polynomially encode metric constraints on the length of the current interval.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
