A tractable subclass of the block algebra : constraint propagation and preconvex relations - Archive ouverte HAL Access content directly
Conference Papers Year : 1999

A tractable subclass of the block algebra : constraint propagation and preconvex relations

(1) , (2) , (2)
1
2

Abstract

We define, in this paper, for every n ≥ 1, n-dimensional block algebra as a set of relations, the block relations, together with the fundamental operations of composition, conversion and intersection. We examine the 13n atomic relations of this algebra which constitute the exhaustive list of the permitted relations that can hold between two blocks whose sides are parallel to the axes of some orthogonal basis in the n-dimensional Euclidean space over the field of real numbers. We organize these atomic relations in ascending order with the intention of defining the concept of convexity as well as the one of preconvexity. We will confine ourselves to the issue of the consistency of block networks which consist of sets of constraints between a finite number of blocks. Showing that the concepts of convexity and preconvexity are preserved by the fundamental operations, we prove the tractability of the problem of the consistency of strongly preconvex block networks, on account of our capacity for deciding it in polynomial time by means of the path-consistency algorithm.

Dates and versions

hal-03300315 , version 1 (27-07-2021)

Identifiers

Cite

Philippe Balbiani, Jean-François Condotta, Luis Farinas del Cerro. A tractable subclass of the block algebra : constraint propagation and preconvex relations. Ninth Portuguese Conference on Artificial Intelligence (EPIA 1999), 1999, Evora, Portugal. pp.75-89, ⟨10.1007/3-540-48159-1_6⟩. ⟨hal-03300315⟩
26 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More