Approximation Algorithms for Temporal Reasoning
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 1291-1295.
Abstract
We consider a representation for temporal relations between intervals introduced by James Allen , and its associated computational or reasoning problem: given possibly indefinite knowledge of the relations between some intervals, how do we compute the strongest possible assertions about the relations between some or all intervals. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable . Allen gives an approximation algorithm based on constraint propagation . We give new approximation algorithms, examine their effectiveness, and determine under what conditions the algorithms are exact.
@inproceedings{ijcai1989p207,
title = {Approximation Algorithms for Temporal Reasoning},
author = {van Beek, Peter},
booktitle = {Proceedings of the Eleventh International Joint Conference on
Artificial Intelligence, {IJCAI-89}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {N. S. Sridharan},
pages = {1291--1295},
year = {1989},
month = {8},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1989/207},
}
TY - CPAPER TI - Approximation Algorithms for Temporal Reasoning AU - van Beek, Peter T2 - Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 PB - International Joint Conferences on Artificial Intelligence PY - 1989 SP - 1291 EP - 1295 UR - https://ijcai.org/proceedings/1989/207 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
