What the Event Calculus Does and How to Do It Efficiently

Kowalski and Sergot's Event Calculus (EC) is a formalism for reasoning about time and change in a logic programming framework. From a description of events which occur in the real world and properties they initiate and terminate, EC allows to derive the maximal time intervals (MVIs) over which properties hold. In this paper, we provide a precise characterization of what EC actually does to compute MVIs, and propose a solution to do it efficiently when incomplete information about event ordering is given. We first introduce the basic features of EC with relative times and partial ordering, and show that it requires an exponential time to compute MVIs for a given property. Then, we show how adopting graph marking techniques reduces the exponential complexity to a polynomial cost. Successively, we formally introduce the notion of kernel of an ordering relation, and show that it can be usefully applied to further reduce the complexity of computing MVIs.