T. K. Satish Kumar
In this paper, we will deal with some important kinds of metric temporal reasoning problems that arise in many real-life situations. In particular, events X_0, X_1 ... X_N are modeled as time points, and a constraint between the execution times of two events X_i and X_j is either simple temporal (of the form X_i - X_j in [a,b]), or has a connected feasible region that can be expressed using a finite set of domain rules each in turn of the form X_i in [a,b] -> X_j in [c,d] (and conversely X_j in [e,f] -> X_i in [g,h]). We argue that such rules are useful in capturing important kinds of non-monotonic relationships between the execution times of events when they are governed by potentially complex (external) factors. Our polynomial-time (deterministic and randomized) algorithms for solving such problems therefore enable us to efficiently deal with very expressive representations of time.
Subjects: 3.6 Temporal Reasoning; 1.12 Scheduling