next up previous
Next: Experimental Results Up: An Efficient Representation and Previous: Computing the of two

An Efficient Inference Procedure for Event Logic

Given the above procedures for computing  tex2html_wrap_inline9682 , tex2html_wrap_inline9704 , tex2html_wrap_inline9736 , tex2html_wrap_inline9792 , tex2html_wrap_inline9964 , and tex2html_wrap_inline10404 , one can now define a procedure for computing tex2html_wrap_inline8918 . This procedure takes a model M along with an event-logic expression  tex2html_wrap_inline8290 and computes a set of normalized spanning intervals that represents the set I of intervals  tex2html_wrap_inline8292 for which tex2html_wrap_inline8294 is true. The model M is a set of atomic event-occurrence formulae of the form tex2html_wrap_inline10582 , where tex2html_wrap_inline10584 is a ground primitive event-logic expression and  tex2html_wrap_inline8292 is a normalized spanning interval. A model entry tex2html_wrap_inline10582 indicates that the primitive event tex2html_wrap_inline10584 occurred during all intervals in the extension of  tex2html_wrap_inline8292 .


The procedure performs structural induction on  tex2html_wrap_inline8290 . It computes a set of normalized spanning intervals to the represent the occurrence of each atomic event-logic expression in  tex2html_wrap_inline8290 and recursively combines the sets so computed for each child subexpression to yield the sets for each parent subexpression. An important property of this inference procedure is that for any finite model M, tex2html_wrap_inline8918 , the set I of intervals  tex2html_wrap_inline8292 for which tex2html_wrap_inline8294 is true, can be represented by a finite set of normalized spanning intervals. Nominally, the number of normalized spanning intervals in tex2html_wrap_inline8918 can be exponential in the subexpression depth of  tex2html_wrap_inline8290 because each step in the structural induction can introduce a constant factor growth in the size of the set. However, in practice, such exponential growth does not occur. Computing tex2html_wrap_inline8918 for all of the event types given in Figure 10 for all of the movies that have been tried so far have yielded sets of fewer than a dozen normalized spanning intervals.

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