A graph-theoretic approach to efficiently reason about partially ordered events in (Modal) Event Calculus

In this paper, we show how well-known graph-theoretic techniques can be successfully exploited to efficiently reason about partially ordered events in Kowalski and Sergot's Event Calculus and in its skeptical and credulous modal variants. To overcome the computational weakness of the traditional generate-and-test algorithm of (Modal) Event Calculus, we propose two alternative graph-traversal algorithms that operate on the underlying directed acyclic graph of events representing ordering information. The first algorithm pairs breadth-first and depth-first visits of such an event graph in a suitable way, while the second one operates on its transitive closure and reduction. We prove the soundness and completeness of both algorithms, and thoroughly analyze and compare their computational complexity. This revised version was published online in June 2006 with corrections to the Cover Date.