ladkin@KESTREL.ARPA (Peter Ladkin) (09/29/87)
There has been much subsequent work done on this topic. I'll try to summarise what I know about. James Allen's system can be formulated as a relation algebra in the sense of Tarski, and also as a complete, countably categorical first-order theory. The theory is thus decidable, and admits of quantifier elimination. This means that arbitrary first-order constraints expressed in the system are computably equivalent to a set of constraints without quantifiers. Such collections of Boolean constraints may be checked for consistency either by an extension of Allen's method, or in other ways. Marc Vilain and Henry Kautz showed that the general constraint satisfaction problem for this system is NP-complete. Allen and Pat Hayes have formulated an alternative theory of time intervals as a collection of first-order axioms. They want to allow the collection of pairs of integers as a model, and thus the axioms are weaker than the original system. These axioms have as models exactly sets of pairs from an unbounded linear order. Johan Van Benthem has investigated interval theories in his book `The Logic of Time'. All the theories are comparable, it turns out, since the collections of primitives are interdefinable. For a reading list, the AAAI-86, AAAI-87, IJCAI-85 and IJCAI-87 conference proceedings contain papers on interval systems for time representation, Allen and Hayes have a technical report (University of Rochester) due out any day, I have also technical reports not in the above sources (Kestrel Institute), and Edward Tsang (University of Essex) has some also. Tom Dean (Brown University) is using interval representations in his planner, and has investigated the most commonly occurring constraint satisfaction problems in detail. Richard Pelavin has incorporated Allen's interval system into the design for a planner, and Henry Kautz has also investigated the use of interval specifications in general planning problems. (Both are former students of James Allen). There is van Benthem's book, and a review of it by Steven Kuhn in the September 1987 Journal of Symbolic Logic (of the open problems mentioned by Kuhn, the first and last were solved already, by Roger Maddux and I, and I'm sure some others). Joe Halpern and Yoav Shoham formulated a modal logic of time with interval modalities, in the First Logic in Computer Science conference (1986, Proceedings published by IEEE). Klaus Schultz at Tubingen has a technical report comparing Allen's approach with Kamp's event theory, and Austin Tate and Colin Bell have investigated the use of interval constraints in the O-Plan planner at Edinburgh (Bell is at the University of Iowa). Other references may be found by taking the transitive closure of the `references' relation on these sources. There is very closely related work being done by Robert Kowalski's group on event structures (Imperial College). Apologies to those whose work I've missed or are unaware of (please let me know). Things are progressing fast, so we all ought to be on each other's mailing lists. peter ladkin ladkin@kestrel.arpa -------