ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS

Computational IntelligencePublished 1 August 1995

Alfonso Gerevini, Lenhart K. Schubert

DOI10.1111/j.1467-8640.1995.tb00043.x

Source URL

Citations13

SJR quartileQ2

SJR score0.58

SNIP1.20

TL;DR

It is shown that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and a new proof is provided showing that the algorithm is indeed correct.

Abstract

We analyze the problem of computing the minimal labels for a network of 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 ≠ ‐relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.

Keywords

Computer Science

Communications of the ACMMaintaining knowledge about temporal intervals

7,550 Citations1983James F. Allen

An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.

View PDF

Artificial IntelligenceConsistency in networks of relations

2,430 Citations1977Alan K. Mackworth

The primary aim is to provide an accessible, unified framework, within which to present the algorithms including a new path consistency algorithm, to discuss their relationships and the may applications, both realized and potential of network consistency algorithms.

Information SciencesNetworks of constraints: Fundamental properties and applications to picture processing

1,248 Citations1974Ugo Montanari

Constraints are treated algebraically, and the solution of a system of linear equations in this algebra provides an approximation of the minimal network, and this solution is proved exact in special cases, e.g., for tree-like and series-parallel networks and for classes of relations for which a distributive property holds.

View PDF

Constraint propagation algorithms for temporal reasoning

643 Citations1986Marc Vilain, Henry Kautz

Computing the consequences of temporal assertions is shown to be computationally intractable in the interval-based representation, but not in the point-based one, but a fragment of the interval language can be expressed using the point language and benefits from the tractability of the latter.

Elsevier eBooksConstraint Propagation Algorithms for Temporal Reasoning: A Revised Report

347 Citations1990Marc Vilain, Henry Kautz +1 more

The present paper departs from the original primarily in correcting claims made there about the point algebra, and in presenting some closely related results of van Beek [1989].

Artificial IntelligenceReasoning about qualitative temporal information

274 Citations1992Peter van Beek

This paper defines computationally efficient procedures for solving two related reasoning tasks that arise in interval and point algebras: Given (possibly indefinite) knowledge of the relationships between some intervals or points, find one or more scenarios that are consistent with the information provided, and find all the feasible relations between every pair of interval or points.

Computational IntelligenceExact and approximate reasoning about temporal relations1

195 Citations1990Peter van Beek, Robin Cohen

This paper addresses a fundamental reasoning task that arises in applications of the algebra: Given (possibly indefinite) knowledge about the relationships between intervals, find all feasible relationships between two intervals, called the minimal labels problem.

Artificial IntelligenceEfficient algorithms for qualitative reasoning about time

78 Citations1995Alfonso Gerevini, Lenhart K. Schubert

This paper addresses the problem of scalability in temporal reasoning by providing a collection of new algorithms for efficiently managing large sets of qualitative temporal relations, focusing on the class of relations forming the Point Algebra (PA-relations) and on a major extension to include binary disjunctions of PA-relations ( PA-disjunctions).

View PDF

The MIT Press eBooksReasoning about qualitative temporal information

71 Citations1994Peter van Beek

This paper develops an O(n2)-time algorithm for finding one consistent scenario that is an 0(n) improvement over the previously known algorithm, and develops an algorithms for finding all the feasible relations that is of far more practical use than the previouslyknown algorithm.

Computational IntelligenceTime revisited1

52 Citations1990Stephanie A. Miller, Lenhart K. Schubert

This paper takes an efficient temporal reasoner and extends its inferential capabilities to handle both strict and nonstrict relations, and the resulting temporal specialist is incorporated into a system intended for low‐level reasoning in natural language understanding.