A Linear-Programming Approach to Temporal Reasoning

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.

Authors

• Peter Jonsson Linköping University

Keywords

No keywords are indexed for this paper.