We present a new formalism, Horn Disjunctive Linear Relations (Horn DLRs), for reasoning about temporal constraints. We prove that deciding satisfiability of sets of Horn DLRs is polynomial by exhibiting an algorithm based upon linear programming. Furthermore, we prove that most other approaches to tractable temporal constraint reasoning can be encoded as Horn DLRs, including the ORD-Horn algebra and most methods for purely quantitative reasoning.
Registration: ISBN 978-0-262-51091-2
Copyright: August 4-8, 1996, Portland, Oregon. Published by The AAAI Press, Menlo Park, California.