Bernhard Nebel and Hans-Juergen Buerckert, "Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra", Journal of the ACM, 1995, Vol. 42, No. 1, pp. 43--66.

One of the main problems of knowledge representation is checking consistency of the expert's knowledge. In particular, we may want to check consistency of the knowledge about time intervals ${\bf t}_i=[t^-_i,t^+_i]$ of different events. In many cases, the experts only have the information about the orderingof different events, e.g., "${\bf t}_i$ starts ${\bf t}_j$", or "${\bf t}_i$ precedes ${\bf t}_j$". This knowledge can be formulated as follows: \begin{itemize} \item we start with basic ordering relations between numbers $a$, $b$: $ab$; \item by applying these relations to endpoints of the intervals ${\bf t}_i$ and ${\bf t}_j$, we get basic ordering relations $R_1,R_2, \ldots,$ between intervals; e.g., "${\bf t}_i$ starts ${\bf t}_j$" can be described as "\$t^-_i=t^-_j\,\&\, t^+_iintractable). Several tractable subclasses of knowledge bases have been proposed, i.e., subclasses for which polynomial-time algorithms can check consistency.

The authors propose a new tractable class that not only contains all previously known tractable classes, but is also maximal in the sense that if we add one more of 8192 possible statements to the list of 868 statements allowed for this class, the class becomes intractable.

This class contains more than 10\% of 8192 possible statements about pairs of intervals, as opposed to previously known subclasses which allow only 1--2\% of statements.