Next: Normalizing Spanning Intervals Up: An Efficient Representation and Previous: An Efficient Representation and

## Spanning Intervals

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.

Next: Normalizing Spanning Intervals Up: An Efficient Representation and Previous: An Efficient Representation and

Jeffrey Mark Siskind
Wed Aug 1 19:08:09 EDT 2001