Next: Spanning Intervals Up: Grounding the Lexical Semantics Previous: Event Logic

An Efficient Representation and Inference Procedure for Event Logic

One might try to implement event logic using only closed intervals of the form [q,r], where . Such a closed interval would represent the set of real numbers. With such closed intervals, one would define Allen's relations as follows:

One difficulty with doing so is that it would be possible for more than one Allen relation to hold between two intervals when one or both of them are instantaneous intervals, such as [q,q]. Both  and  would hold between [q,q] and [q,r], both  and  would hold between [q,r] and [q,q], both  and  would hold between [q,r] and [r,r], both  and  would hold between [r,r] and [q,r], and =, , and  would all hold between [q,q] and itself. To create a domain where exactly one Allen relation holds between any pair of intervals, let us consider both open and closed intervals. Closed intervals contain their endpoints while open intervals do not. The intervals (q,r], [q,r), and (q,r), where q<r, represent the sets , , and of real numbers respectively. The various kinds of open and closed intervals can be unified into a single representation , where  and  are true or false to indicate the interval being closed or open on the left or right respectively. More specifically, denotes [q,r], denotes (q,r], denotes [q,r), and denotes (q,r). To do this, let us use to mean when  is true and q<r when  is false. Similarly, let us use to mean when  is true and q>r when  is false. More precisely, and . With these, represents the set of real numbers.

One can extend the definition of Allen's relations to both open and closed intervals as follows. The relation holds if the corresponding endpoints of  and  are equal and have the same openness. The relation holds if the right endpoint of  precedes the left endpoint of  or if they are equal and both open. For example, [1,3]<[4,5] and [1,3)<(3,5], but , , and . The relation holds if the right endpoint of  equals the left endpoint of  and one of those endpoints is open while the other is closed. For example, and but and . The relation holds if

• either the left endpoint of  precedes the left endpoint of  or they are equal while the former is closed and the latter is open,
• either the left endpoint of  precedes the right endpoint of  or they are equal while both endpoints are closed, and
• either the right endpoint of  precedes the right endpoint of  or they are equal while the former is open and the latter is closed.
For example, , , , and , but , , and . The relation holds if
• the left endpoints of  and  are equal and have the same openness and
• either the right endpoint of  precedes the right endpoint of  or they are equal while the former is open and the latter is closed.
For example, , , and , but , , , and . The relation holds if
• the right endpoints of  and  are equal and have the same openness and
• either the left endpoint of  follows the left endpoint of  or they are equal while the former is open and the latter is closed.
For example, , , and , but , , , and . The relation holds if
• either the left endpoint of  follows the left endpoint of  or they are equal while the former is open and the latter is closed and
• either the right endpoint of  precedes the right endpoint of  or they are equal while the former is open and the latter is closed.
For example, and , but , , , and . The inverse Allen relations >, , , , , and are defined analogously to the <, , , , , and relations respectively with the arguments reversed.

The above definitions can be stated more precisely as follows:

With the above definitions, exactly one Allen relation holds between any pair of intervals.

I refer to the set of real numbers represented by an interval as its extension. Given the above definition of interval, any interval, such as [5,4], (5,4], [5,4), or (5,4), where the upper endpoint is less than the lower endpoint represents the empty set. Furthermore, any open interval, such as [5,5), (5,5], or (5,5), where the upper endpoint equals the lower endpoint also represents the empty set. To create a situation where the extension of each interval has a unique representation, let us represent all such empty sets of real numbers as  . Thus whenever we represent an interval explicitly, it will have a nonempty extension and will satisfy the following normalization criterion: .

Next: Spanning Intervals Up: Grounding the Lexical Semantics Previous: Event Logic

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