Temporal Reasoning about Two Concurrent Sequences of Events

This paper discusses temporal reasoning with respect to constraints on two concurrent sequences of events. If two given sequences of events can be mapped into one sequence that satisfies a given constraint, then the constraint is said to be consistent. First, we mention that the consistency of such constraints is NP-complete. Then we introduce the notion of graph representations of constraints. If a graph representation of a given constraint c can be constructed in polynomial time, then the consistency of c is decidable in polynomial time. However, it is shown that the graph representability of a given c is coNP-complete. Next, we propose a subclass CDC$^{\neq} of constraints such that for each constraint c in CDC$^{\neq}$, a graph representation of c can be constructed in polynomial time. The expressive power of CDC$^{\neq}$ is incomparable to any other subclasses of constraints for which the consistency problem is known to be tractable