Discrete-Time Temporal Reasoning with Horn DLRs

Jonsson, Peter; Lööw, Tomas

doi:10.5591/978-1-57735-516-8/IJCAI11-161

Discrete-Time Temporal Reasoning with Horn DLRs

Peter Jonsson, Tomas Lööw

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 931-935.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-161

Abstract

Temporal reasoning problems arise in many areas of AI, including planning, natural language understanding, and reasoning about physical systems. The computational complexity of continuous-time temporal constraint reasoning is fairly well understood. There are, however, many different cases where discrete time must be considered; various scheduling problems and reasoning about sampled physical systems are two examples. Here, the complexity of temporal reasoning is not as well-studied nor as well-understood. In order to get a better understanding, we consider the powerful Horn DLR formalism adapted for discrete time and study its computational complexity. We show that the full formalism is NP-hard and identify several maximal tractable subclasses. We also ‘lift’ the maximality results to obtain hardness results for other families of constraints. Finally, we discuss how the results and techniques presented in this paper can be used for studying even more expressive classes of temporal constraints.

Peter Jonsson, and Tomas Lööw. 2011. Discrete-Time Temporal Reasoning with Horn DLRs. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 931–935. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-161

@inproceedings{ijcai2011p161,
  title     = {Discrete-Time Temporal Reasoning with Horn DLRs},
  author    = {Jonsson, Peter and Lööw, Tomas},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {931--935},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-161},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-161},
}

TY  - CPAPER
TI  - Discrete-Time Temporal Reasoning with Horn DLRs
AU  - Jonsson, Peter
AU  - Lööw, Tomas
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 931
EP  - 935
DO  - 10.5591/978-1-57735-516-8/IJCAI11-161
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-161
ER  -