Replaceability and the substitutability hierarchy for constraint satisfaction problems
Refereed Conference Meeting Proceeding
Problem simplification is a topic of continuing interest in the field of constraint satisfaction. In this paper we examine properties associated with the basic idea of substitutability and show how certain forms of substitutability can be organized into a well-formed hierarchy. One of these properties, here called replaceability, has been identified by other authors as being of special interest. In this work we confirm these earlier claims and show that replaceability is significant because it is the most general property in the hierarchy that allows us to make inferences from local to global versions of this property. To make use of this discovery, we introduce two algorithms for establishing neighbourhood replaceability, and we present an initial experimental examination of these algorithms including ways to improve their performance through ordering heuristics and various kinds of inference.
Third Global Conference on Artificial Intelligence - GCAI 2017
Digital Object Identifer (DOI):
United States of America
National University of Ireland, Cork (UCC)
Open access repository: