A Linear-Programming Approach to Temporal Reasoning

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

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.