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 CDCnot equal of constraints such that for each constraint c in CDCnot equal, a graph representation of c can be constructed in polynomial time. The expressive power of CDCnot equal is incomparable to any other subclasses of constraints for which the consistency problem is known to be tractable.
temporal reasoning consistency temporal constraint complexity