When using event logic, we wish to compute and represent the set *I* of all
intervals over which some event-logic expression holds.
Many event types, including all of the primitive event types used in LEONARD,
are *liquid* [48] in the sense that if some event holds of an
interval then that event holds of every subinterval of that interval.
With real-valued interval endpoints, this creates the need to compute and
represent an infinite set of intervals for a liquid event.
Even limiting ourselves to integer-valued interval endpoints, a liquid event
will require the computation and representation of quadratically many
intervals.

To address this problem, let us introduce the notion of *spanning
interval*.
A spanning interval represents the set of all subintervals of
[*i*,*j*], in other words
.
Similarly , , and represent
,
, and
respectively.
We wish to use spanning intervals to represent the set of all
intervals over which the primitive event types hold and to compute and
represent the set of all intervals over which compound event types hold via
structural induction over the compound event-logic expressions.
A problem arises however.
Given two liquid event types and , the compound event
type is not liquid.
If holds over and holds over , then
might not hold over every subinterval of [*i*,*k*).
It holds over only those subintervals that include *j*.
For example, if holds over and holds over
then holds for every interval that starts between 1
and 10 and ends between 8 and 20.
But it doesn't hold for every subinterval of [1,20).
For example, it doesn't hold of [12,20).
I refer to such event types as *semi liquid*.
Since spanning intervals are not sufficient to efficiently represent
semi-liquid events, let us extend the notion of spanning interval.
A spanning interval [[*i*,*j*],[*k*,*l*]] represents the set of intervals
.
Similarly the spanning intervals ([*i*,*j*],[*k*,*l*]], [[*i*,*j*],[*k*,*l*]),
and ([*i*,*j*],[*k*,*l*]) represent the sets
,
, and
respectively.
This extended notion of spanning interval subsumes the original notion.
The spanning intervals , , , and
can be represented as the spanning intervals [[*i*,*j*],[*i*,*j*]],
([*i*,*j*],[*i*,*j*]], [[*i*,*j*],[*i*,*j*]), and ([*i*,*j*],[*i*,*j*]) respectively.
For reasons that will become apparent in Section 4.4, it is
necessary to also allow for spanning intervals where the ranges of endpoint
values are open.
In other words, we will need to consider spanning intervals
like [(*i*,*j*],[*k*,*l*]] to represent sets like
.
All told, there are six endpoints that can independently be either open or
closed, namely *q*, *r*, *i*, *j*, *k*, and *l*, yielding sixty four kinds of
spanning intervals.
These can all be unified into a single representation
,
where , , , , , and are true
or false if the endpoints *q*, *r*, *i*, *j*, *k*, and *l* are closed or open
respectively.
More precisely, the spanning interval
represents the set

of intervals.
I refer to the set of intervals represented by a spanning interval as its
*extension*.
Moreover, a set of spanning intervals will represent the union of the
extensions of its members.
Additionally, the empty set of spanning intervals will represent the empty set
of intervals.
I further refer to the set of intervals represented by a set of spanning
intervals as its *extension*.
A key result of this paper is that if the set of all intervals over which some
set of primitive event types hold can be represented as finite sets of spanning
intervals then the set of all intervals over which all event types that are
expressible as compound event-logic expressions over those primitives hold
can also be represented as finite sets of spanning intervals.

While we require that all intervals have finite endpoints, for reasons that will also become apparent in Section 4.4, it is necessary to allow spanning intervals to have infinite endpoints, for example . Such spanning intervals with infinite endpoints represent sets of intervals with finite endpoints but where the range of possible endpoints is unconstrained from above or below.

Wed Aug 1 19:08:09 EDT 2001