Skip to Main content Skip to Navigation
Conference papers

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

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.
Document type :
Conference papers
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03300315
Contributor : Fabien Delorme <>
Submitted on : Tuesday, July 27, 2021 - 9:34:51 AM
Last modification on : Saturday, September 4, 2021 - 3:20:07 AM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

39