next up previous
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 tex2html_wrap_inline9066 . Such a closed interval would represent the set tex2html_wrap_inline9068 of real numbers. With such closed intervals, one would define Allen's relations as follows:

eqnarray1170

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  tex2html_wrap_inline8372 and  tex2html_wrap_inline8380 would hold between [q,q] and [q,r], both  tex2html_wrap_inline8374 and  tex2html_wrap_inline8382 would hold between [q,r] and [q,q], both  tex2html_wrap_inline8372 and  tex2html_wrap_inline8386 would hold between [q,r] and [r,r], both  tex2html_wrap_inline8374 and  tex2html_wrap_inline8384 would hold between [r,r] and [q,r], and =, tex2html_wrap_inline8372 , and  tex2html_wrap_inline8374 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 tex2html_wrap_inline9120 , tex2html_wrap_inline9122 , and tex2html_wrap_inline9124 of real numbers respectively. The various kinds of open and closed intervals can be unified into a single representation tex2html_wrap_inline9126 , where  tex2html_wrap_inline9128 and  tex2html_wrap_inline9130 are true or false to indicate the interval being closed or open on the left or right respectively.gif More specifically, tex2html_wrap_inline9170 denotes [q,r], tex2html_wrap_inline9174 denotes (q,r], tex2html_wrap_inline9178 denotes [q,r), and tex2html_wrap_inline9182 denotes (q,r). To do this, let us use tex2html_wrap_inline9186 to mean tex2html_wrap_inline9066 when  tex2html_wrap_inline9128 is true and q<r when  tex2html_wrap_inline9128 is false. Similarly, let us use tex2html_wrap_inline9196 to mean tex2html_wrap_inline9198 when  tex2html_wrap_inline9128 is true and q>r when  tex2html_wrap_inline9128 is false. More precisely, tex2html_wrap_inline9206 and tex2html_wrap_inline9208 . With these, tex2html_wrap_inline9126 represents the set tex2html_wrap_inline9212 of real numbers.

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

For example, tex2html_wrap_inline9264 , tex2html_wrap_inline9266 , tex2html_wrap_inline9268 , and tex2html_wrap_inline9270 , but tex2html_wrap_inline9272 , tex2html_wrap_inline9274 , and tex2html_wrap_inline9276 . The relation tex2html_wrap_inline9278 holds if For example, tex2html_wrap_inline9288 , tex2html_wrap_inline9290 , and tex2html_wrap_inline9292 , but tex2html_wrap_inline9294 , tex2html_wrap_inline9296 , tex2html_wrap_inline9298 , and tex2html_wrap_inline9300 . The relation tex2html_wrap_inline9302 holds if For example, tex2html_wrap_inline9312 , tex2html_wrap_inline9314 , and tex2html_wrap_inline9316 , but tex2html_wrap_inline9318 , tex2html_wrap_inline9320 , tex2html_wrap_inline9322 , and tex2html_wrap_inline9324 . The relation tex2html_wrap_inline9326 holds if For example, tex2html_wrap_inline9336 and tex2html_wrap_inline9338 , but tex2html_wrap_inline9340 , tex2html_wrap_inline9342 , tex2html_wrap_inline9344 , and tex2html_wrap_inline9346 . The inverse Allen relations >, tex2html_wrap_inline8374 , tex2html_wrap_inline8378 , tex2html_wrap_inline8382 , tex2html_wrap_inline8386 , and tex2html_wrap_inline8390 are defined analogously to the <, tex2html_wrap_inline8372 , tex2html_wrap_inline8376 , tex2html_wrap_inline8380 , tex2html_wrap_inline8384 , and tex2html_wrap_inline8388 relations respectively with the arguments reversed.

The above definitions can be stated more precisely as follows:

             eqnarray1308

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  tex2html_wrap_inline9386 . Thus whenever we represent an interval tex2html_wrap_inline9126 explicitly, it will have a nonempty extension and will satisfy the following normalization criterion: tex2html_wrap_inline9390 .




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

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