UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

The complexity of constraint satisfaction problems for small relation algebras

Cristani, M; Hirsch, R; (2004) The complexity of constraint satisfaction problems for small relation algebras. Artificial Intelligence , 156 (2) 177 - 196. 10.1016/j.artint.2004.02.003.

Full text not available from this repository.

Abstract

Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras - those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra. In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity. We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete. © 2004 Elsevier B.V. All rights reserved.

Type:Article
Title:The complexity of constraint satisfaction problems for small relation algebras
DOI:10.1016/j.artint.2004.02.003
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record