A Fast Algorithm for Consistency Checking Partially Ordered Time

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). This is achieved by a sophisticated enumeration of structures similar to total orders, which are then greedily expanded towards 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. Qualitative reasoning is an important formalism in artificial intelligence where the objective is to reason about continuous properties given certain relations between the unknown entities. Two important subfields are temporal reasoning, e.g., the point algebra for partially ordered time (POT), Allen's interval algebra (A), and the point algebra for branching time, and spatial reasoning, e.g., the region connection calculus (RCC), the cardinal direction calculus, and the rectangle algebra.