ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS

Authors
GEREVINI A SCHUBERT L
Citation
A. Gerevini et L. Schubert, ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS, Computational intelligence, 11(3), 1995, pp. 443-448
Citations number
15
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Artificial Intelligence
Journal title
Computational intelligence → ACNP
ISSN journal
08247935
Volume
11
Issue
3
Year of publication
1995
Pages
443 - 448
Database
ISI
SICI code
0824-7935(1995)11:3<443:OCTMLI>2.0.ZU;2-8
Abstract
We analyze the problem of computing the minimal labels for a network o f temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O (max(n(3), n(2) . m)) time (for n points and m not equal-relations). We show that the proof of th e correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed corre ct.