A complete classification of tractability in Allen's algebra relative to subsets of basic relations. - Drakengren, Thomas; Jonsson, Peter
We characterise the set of subalgebras of Allen's algebra which have anext term tractable satisfiability problem, and in addition contain certain basic relations. The conclusion is that no tractable subalgebra dial is not known in the literature can contain more than the three basic relations (≡), (b) and (bsucceeds or equal to), where b ε d, o, , f. This means that concerning algebras for specifying completen knowledge about temporal information, there is no hope of finding yet unknown classes with much expressivity. We also classify completely some cases where we cannot even express complete information (but close to complete), showing that there are exactly two maximal tractable algebras containing the relation (precedes succeeds), exactly two containing the relation (precedes succeeds m m≤), and exactly three containing the relation (precedes m). The algebras containing (precedes succeeds) can express the notion of sequentiality; thus we have a complete characterization of tractable inference using that notion.
Keywords: Temporal reasoning; Computational complexity; Allen's algebra; Tractability; Complete classification