CLASSIFYING THE COMPLEXITY OF TEMPORAL CONSTRAINTS
Dr Andrei Krokhin, Computing Laboratory, University of Oxford

Abstract: Reasoning about temporal constraints is an important task in many areas of computer science and elsewhere, such as scheduling, planning, technical diagnosis, molecular biology, and archeology. Several frameworks for formalizing this type of problem have been suggested; for instance, the point algebra (for expressing relations between time points), the point-interval algebra (for expressing relations between time points and intervals) and the famous Allen's interval algebra for expressing relations between time intervals. This algebra has proven to be useful and convenient and it has also become the kernel of some other formalisms.

Due to computational hardness (the basic satisfiability problem in Allen's algebra is NP-complete), it is unlikely that efficient algorithms exist for reasoning in the full algebra. This computational difficulty has motivated the study of the complexity of fragments of the algebra, and the search for effective heuristics based on tractable fragments.

In this talk we present a complete classification of complexity in Allen's algebra.

This is joint work with Peter Jeavons (Oxford University) and Peter Jonsson (Linkoeping University, Sweden)

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 5 March 2001.

back