Skip to Main content Skip to Navigation
Journal articles

Tractability results in the block algebra

Abstract : In this paper we define the notion of a block algebra, which is based upon a spatial application of Allen's interval algebra. In the pddimensional Euclidean space, where p g 1, we consider only blocks whose sides are parallel to the axes of some orthogonal basis. The block algebra consists of a set of relations (the block relations) together with the fundamental operations of composition, converse and intersection. The 13 p basic relations of this algebra constitute the exhaustive list of the relations possibly holding between two blocks. We are interested in the problem of testing the consistency of a set of spatial constraints between blocks, i.e. a block network. The consistency question for block networks is NPdcomplete. We first extend the notions of convexity and preconvexity to the block algebra. Similarly to the interval algebra case, convexity leads to a tractable set whereas, contrary to the interval algebra case, preconvexity leads to an intractable set. Nevertheless we characterize a tractable subset of the preconvex relations: the strongly preconvex relations. Moreover we show that strong preconvexity and ORDdHorn representability are the same.
Document type :
Journal articles
Complete list of metadata
Contributor : Fabien Delorme Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 9:16:51 AM
Last modification on : Tuesday, October 19, 2021 - 2:23:38 PM

Links full text



Philippe Balbiani, Jean-François Condotta, Luis Farinas del Cerro. Tractability results in the block algebra. Journal of Logic and Computation, Oxford University Press (OUP), 2002, 12 (5), pp.885-909. ⟨10.1093/logcom/12.5.885⟩. ⟨hal-03300288⟩



Les métriques sont temporairement indisponibles