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

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 <i> ordering</I>of 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 <I> basic</I> ordering relations between numbers
$a$, $b$: $a<b$,
$a=b$, and $a>b$;
\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^+_i<t^+_j$"; 
\item since expert knowledge can be incomplete, the knowledge about a
given pair of events can be expressed as a statement 
$({\bf t}_i R_k {\bf t}_j) \vee
\ldots\vee ({\bf t}_i R_l {\bf t}_j)$ for some basic relations
$R_k,\ldots,R_l$; there are 8192 possible statements of this type;
\item a {\it knowledge base} is a conjunction of statements about
different pairs of events.
\end{itemize}
It is known that checking consistency of such knowledge bases is
NP-hard (<i>intractable</I>). 
Several <I> tractable</I> subclasses of knowledge bases 
have been proposed, i.e., subclasses for which
polynomial-time algorithms can check consistency. 
<P>
The authors propose a new tractable class that not only
contains all previously known tractable classes, but
is also <I> maximal</I> 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. 
<P>
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.