A tractable subclass of the block algebra : constraint propagation and preconvex relations - Université d'Artois Accéder directement au contenu
Communication Dans Un Congrès Année : 1999

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

Résumé

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 et versions

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

Identifiants

Citer

Philippe Balbiani, Jean-François Condotta, Luis Fariñas del Cerro. A tractable subclass of the block algebra : constraint propagation and preconvex relations. 9th Portuguese Conference on Artificial Intelligence (EPIA 1999), Sep 1999, Evora, Portugal. pp.75-89, ⟨10.1007/3-540-48159-1_6⟩. ⟨hal-03300315⟩
36 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More