Just as we desire that the extension of every interval have a unique
representation, we also desire that the extension of every spanning interval
have a unique representation.
There are a number of situations where two different spanning intervals will
have the same extension.
First, all spanning intervals
where , , , or represent the empty
set of intervals, because there are no intervals with an endpoint that is less
than or equal to minus infinity or greater than or equal to infinity.
Second, if , , , or , the value
of , , , or does not affect the denotation
respectively, because there are no intervals with infinite endpoints.
Third, if *j*>*l*, *j* can be decreased as far as *l* without changing the
denotation, because all intervals where the upper endpoint is less than the
lower endpoint equivalently denote the empty interval.
Similarly, if *k*<*i*, *k* can be increased as far as *i* without changing the
denotation.
Fourth, all spanning intervals where *i*>*j* or *k*>*l* represent the empty set of
intervals, because the range of possible endpoints would be empty.
Fifth, all spanning intervals where *i*=*j* and either or is
false (indicating an open range for the lower endpoint) represent the empty
set of intervals, because the range of possible endpoints would be empty.
Similarly, all spanning intervals where *k*=*l* and either or
is false (indicating an open range for the upper endpoint) also represent the
empty set of intervals.
Sixth, all spanning intervals where *i*=*l* and either or is
false (indicating an open interval) also represent the empty set of intervals,
because the endpoints of an open interval must be different.
Seventh, if *j*=*l* and is false, the
value of does not affect the denotation, because if *j*=*l* and
is false, the upper endpoint must be less than *l* and the lower endpoint must
be less than or equal to *j* which equals *l*, so the lower endpoint must be
less than *j*.
Similarly, if *k*=*i* and is false, the value of does not
affect the denotation.
Eighth, if *j*=*l* and either or is false, the
value of does not affect the denotation, because the lower endpoint
of an open interval must be less than its upper endpoint.
Similarly, if *k*=*i* and either or is false, the
value of does not affect the denotation.

To create a situation where the extension of every spanning interval has a
unique representation, let us represent all empty sets of intervals
as .
When the values of *i*, *j*, *k*, *l*, , , ,
, , or can be changed without changing the
denotation, we will select the tightest such values.
In other words, false values for the Boolean parameters, maximal values for
the lower bounds, and minimal values for the upper bounds.
Thus whenever we represent a spanning interval
explicitly, it will have a nonempty extension and will satisfy the following
normalization criterion:

Criteria (1) through (8) correspond to points one through eight above.

A spanning interval
is
*normalized* if *i*, *j*, *k*, *l*, , , , ,
, and cannot be changed without changing its denotation.
Given a (potentially non-normalized) spanning interval , its
*normalization* is the smallest set of normalized spanning
intervals that represents the extension of .
One can compute as follows:

An important property of spanning intervals is that for any spanning
interval , contains at most *one* normalized spanning
interval.

Wed Aug 1 19:08:09 EDT 2001