---
title: "Managing Efficiently Temporal Relations Through Indexed Spanning Trees"
authors:
  - "Malik Ghallab"
  - "A. Mounir Alaoui"
doi: ""
url: "https://ijcai.org/proceedings/1989/208"
pdf: "https://ijcai.org/proceedings/1989/0208.pdf"
venue: "Proceedings of the Eleventh International Joint Conference on Artificial Intelligence"
year: 1989
pages: "1297-1302"
track: "Knowledge Representation"
keywords:
---

# Managing Efficiently Temporal Relations Through Indexed Spanning Trees

Malik Ghallab, A. Mounir Alaoui

*Proceedings of the Eleventh International Joint Conference on Artificial Intelligence*, 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.