# A Fast Algorithm for Consistency Checking Partially Ordered Time

# A Fast Algorithm for Consistency Checking Partially Ordered Time

## Leif Eriksson, Victor Lagerkvist

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence

Main Track. Pages 1911-1918.
https://doi.org/10.24963/ijcai.2023/212

Partially ordered models of time occur naturally in applications where agents/processes cannot perfectly communicate with each other, and can be traced back to the seminal work of Lamport. In this paper we consider the problem of deciding if a (likely incomplete) description of a system of events is consistent, the network consistency problem for the point algebra of partially ordered time (POT). While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT except that it can
be solved in O*((0.368n)^n) time by enumerating ordered partitions. We construct a much faster algorithm with a run-time bounded by O*((0.26n)^n), which, e.g., is roughly 1000 times faster than the naive enumeration algorithm in a problem with 20 events. This is achieved by a sophisticated enumeration of structures similar to total orders, which are then greedily expanded toward a solution. While similar ideas have been explored earlier for related problems it turns out that the analysis for POT is non-trivial and requires significant new ideas.

Keywords:

Constraint Satisfaction and Optimization: CSO: Constraint satisfaction

Knowledge Representation and Reasoning: KRR: Qualitative, geometric, spatial, and temporal reasoning