**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Wed, 28 Sep 2016 12:16:39 *

Drakengren, T. and Jonsson, P. (1996).
** Maximal Tractable
Subclasses of Allen's Interval Algebra: Preliminary Report**.
Technical Report LiTH-IDA-R-96-14, Department of Computer and Information
Science, Linköping University, Sweden.
(bibtex),

**Abstract: **This paper continues Nebel and B{\"u}rckert's
investigation of Allen's interval algebra by presenting nine more maximal
tractable subclasses of the algebra (unless P=NP), in addition to their
previously reported ORD-Horn subclass. 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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*