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.