Robin Hirsch, "From points to intervals", Journal of Applied Non-Classical Logics, 1994, Vol. 4, No. 1, pp. 7--27.

In traditional interval computations, an interval is defined as a pair of numbers. In knowledge representation, we may define time interval corresponding to an event as a pair of numbers if we are only interested in the moments of time when the event started and ended; but we can also add additional information: e.g., we can describe what exactly happens at each endpoint, what properties of the situation hold at each of these moments of time, etc.

In the paper under review, the author describes a general way to get such generalized intervals from generalized "points" (i.e., numbers with additional information). Namely, let a set of points be already defined. This means that we have a set $S$ whose elements will be called "points", and we have a set $\cal R$ of binary relations $R(s,s')$ between points; we will called these relations basic. We can then define intervals as pairs of points $(s^-,s^+)$, $s^-\in S$, $s^+\in S$, and we can define {\it basic relations} between intervals $(s^-,s^+)$ and $(t^-,t^+)$ as relations of the type $R_1(s^-,t^-)\,\&\, R_2(s^-,t^+)\,\&\, R_3(s^+,t^-)\,\&\, R_4(s^+,t^+)$, where $R_i$ are basic relations between points.

In particular, if we take $S=R$ and ${\cal R}=\{<,=,>\}$, we get Allen's interval algebra; if we take $S=R$ and ${\cal R}$ consisting of the relations $s'-s\in [a,b]$ for different intervals $[a,b]$, we get a metric version of interval algebra.

We can apply the above-defined pairing operation to intervals teated as "points", and get intervals of intervals (usually called twins in interval computations).

A natural question is: suppose that we know that for some finite set of objects $x_1,\ldots,x_n$ (points or intervals), a set of relations of the type $R_1(x_i,x_j)\vee ...\vee R_m(x_i,x_j)$ holds. Is this knowledge consistent?

Going from points to intervals can drastically increase the computational complexity of this consistency-checking problem: for points with ordinal or metric relations consistency can be checked by a cubic time algorithm; for intervals, consistency problem is NP-hard even for ordering relations only.