A Representation for Efficient Temporal Reasoning

It has been observed that the temporal reasoning component in a knowledge-based system is frequently a bottleneck. We investigate here a class of graphs appropriate for an interesting class of temporal domains and for which very efficient algorithms for reasoning are obtained, that of series-parallel graphs. These graphs can be used for example to model process execution, as well as various planning or scheduling activities. Events are represented by nodes of a graph and relationships are represented by edges labeled by 5 or <. Graphs are composed using a sequence of series and pcaraldel steps (recursively) on series-parallel graphs. We show that there is an 0(n) time preprocessing algorithm that allows us to answer queries about the events in O(1) time. Our results make use of a novel embedding of the graphs on the plane that is of independent interest. Finally we argue that these results may be incorporated in general graphs representing temporal events by extending the approach of Gerevini and Schubert.

Authors

• James P. Delgrande

Keywords

No keywords are indexed for this paper.