A Hierarchy of Modal Event Calculi: Expressiveness and Complexity

We consider a hierarchy of modal event calculi to represent and reason about partially ordered events. These calculi are based on the model of time and change of Kowalski and Sergot's Event Calculus (EC): given a set of event occurrences, EC allows the derivation of the maximal validity intervals (MVIs) over which properties initiated or terminated by those events hold. The formalisms we analyze extend EC with operators from modal logic. They range from the basic Modal Event Calculus (MEC), that computes the set of all current MVIs (MVIs computed by EC) as well as the sets of MVIs that are true in some/every refinement of the current partial ordering of events (Diamond-Box-MVIs), to the Generalized Modal Event Calculus (GMEC), that extends MEC by allowing a free mix of boolean connectives and modal operators. We analyze and compare the expressive power and the complexity of the proposed calculi, focusing on intermediate systems between MEC and GMEC. We motivate the discussion by using a fault diagnosis problem as a case study.