Global Consistency in Interval Algebra Networks: Tractable Subclasses.
Christian Bessière, Amar Isli, Gérard Ligozat · 1996
. Global consistency is an important property in binary constraint satisfaction problems. It implies minimality in the sense that the edges contain all and only the labels that can participate in a global solution, which, for instance, is an important property in querying temporal knowledge bases. Another, computational, advantage of a globally consistent network is that finding a solution can be done in a backtrackfree manner. In this paper, we propose two new subclasses of the interval algebra for which path-consistency is sufficient to ensure global consistency, i.e. path-consistency applied to any network expressed in either of the two subclasses leads to a globally consistent network. One of the two subclasses covers more than 60% of the ORD-Horn subclass. Keywords: Complexity of Reasoning, Constraint-Based Reasoning, Temporal Reasoning. 1 INTRODUCTION Representing and reasoning about temporal information is essential in many artificial intelligence applications such as natural ...