Maximal Tractable Subclasses of Allen’s Interval Algebra: Preliminary Report

This paper continues Nebel and Biirckert’ s investigation of Allen’ s interval algebra by presenting nine more maximal tractable subclasses of the algebra (provided that P # NP), in addition to their previously reported ORD-HO~PEsubclass. Furthermore, twelve tractable subclasses are identified, whose maximality is not decided. Four of these can express the notion of sequentiality between intervals, which is not possible in the ORD-Horn algebra. The satisfiability algorithm, which is common for all the algebras, is shown to be linear.

Authors

• Thomas Drakengren Peter Jonsson

Keywords

No keywords are indexed for this paper.