There are thirteen * basic* relations that can hold between
two intervals
(see Figure 1; [2,6]).
In order to represent indefinite
information, the relation between two intervals is allowed to be
a disjunction of the basic relations. Sets are used to list the
disjunctions. For example, the relation {m,o,s} between events
A and B represents the disjunction,

Let *I* be the set of all basic relations,
{b,bi,m,mi,o,oi,s,si,d,di,f,fi,eq}. Allen allows the relation
between two events to be any subset of *I*.

**Figure 1:** Basic relations between intervals

We use a graphical notation where vertices represent events and
directed edges are labeled with sets of basic relations. As a
graphical convention, we never show the edges (*i, i*), and if we
show the edge (*i, j*), we do not show the edge (*j, i*). Any
edge for which we have no explicit knowledge of the relation is
labeled with *I*; by convention such edges are also not shown.
We call networks with labels that are arbitrary subsets of *I*,
interval algebra or IA networks.

** Example 1.**
Allen and Koomen [3] show how IA networks can be
used in non-linear planning with concurrent actions. As an
example of representing temporal information using IA
networks, consider the following blocks-world planning problem.
There are three blocks, A, B, and C. In the initial state, the
three blocks are all on the table. The goal state is simply a
tower of the blocks with A on B and B on C. We associate states,
actions, and properties with the intervals they hold over, and we
can immediately write down the following temporal information.

*Initial Conditions*- Initial {d} Clear(A)
- Initial {d} Clear(B)
- Initial {d} Clear(C)
*Goal Conditions*- Goal {d} On(A,B)
- Goal {d} On(B,C)

*Stacking Action*- Stack(A,B) {bi,mi} Initial
- Stack(A,B) {d} Clear(A)
- Stack(A,B) {f} Clear(B)
- Stack(A,B) {m} On(A,B)
*Stacking Action*- Stack(B,C) {bi,mi} Initial
- Stack(B,C) {d} Clear(B)
- Stack(B,C) {f} Clear(C)
- Stack(B,C) {m} On(B,C)

An IA network is * consistent* if and only if there
exists a mapping *M* of a real interval *M*(*u*) for each event or
vertex *u* in the network such that the relations between events
are satisfied (i.e., one of the disjuncts is satisfied). For
example, consider the small subnetwork in Figure 2a
consisting of the events On(A,B), On(B,C), and Goal. This
subnetwork is consistent as demonstrated by the assignment,
*M*(On(A,B)) = [1,5],
*M*(On(B,C)) = [2,5], and
*M*(Goal) = [3,4].
If we were to change the subnetwork and insist that On(A,B) must
be before On(B,C), no such mapping would exist and the subnetwork
would be inconsistent.

A * consistent scenario* of an IA network is a
non-disjunctive subnetwork (i.e., every edge is labeled with a
single basic relation) that is consistent. In our planning
example, finding a consistent scenario of the network corresponds
to finding an ordering of the actions that will accomplish the
goal of stacking the three blocks. One such consistent scenario
can be reconstructed from the qualitative mapping shown in
Figure 2b.

**Figure 2:** Representing qualitative relations between intervals

** Example 2.**
Golumbic and Shamir [12] discuss how IA networks
can be used in a problem in molecular biology: examining the
structure of the DNA of an organism [4]. The
intervals in the IA network represent segments of DNA.
Experiments can be performed to determine whether a pair of
segments is either disjoint or intersects. Thus, the IA
networks that result contain edges labeled with disjoint
({b,bi}), intersects ({m,mi,o,oi,s,si,d,di,f,fi,eq}), or *I*,
the set of all basic relations---which indicates no experiment
was performed. If the IA network is consistent, this is
evidence for the hypothesis that DNA is linear in structure; if
it is inconsistent, DNA is nonlinear (it forms loops, for
example). Golumbic and Shamir [12] show that
determining consistency in this restricted version of IA
networks is NP-complete. We will show that problems that arise
in this application can often be solved quickly in practice.