Managing Efficiently Temporal Relations Through Indexed Spanning Trees
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 1297-1302.
Abstract
We are interested here in the design of a very efficient Time-Map Manager, able to deal with a large knowledge-base of several thousand time-tokens in demanding applications such as reactive planning and execution control. A system, called IxTeT, aiming at that goal is described. It uses an original representation of a lattice of time-points that relies for efficiency on a maximum spanning tree of the lattice together with a particular indexing of its nodes. The lxTeT system is sound and complete, it has the same expressive power as the restricted Interval Algebra that permits completeness in polynomial time. Its average complexity is shown experimentally to be linear, with a low overhead constant, for both operations: retrieval in and updating of a set of temporal relations.
@inproceedings{ijcai1989p208,
title = {Managing Efficiently Temporal Relations Through Indexed Spanning Trees},
author = {Ghallab, Malik and Alaoui, A. Mounir},
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 = {1297--1302},
year = {1989},
month = {8},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1989/208},
}
TY - CPAPER TI - Managing Efficiently Temporal Relations Through Indexed Spanning Trees AU - Ghallab, Malik AU - Alaoui, A. Mounir T2 - Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 PB - International Joint Conferences on Artificial Intelligence PY - 1989 SP - 1297 EP - 1302 UR - https://ijcai.org/proceedings/1989/208 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
