Access to this article is restricted until 12 months after publication by request of the publisher. Restriction lift date: 2026-06-14
Replaceability and a simple substitutability hierarchy for constraint satisfaction problems
Loading...
Files
Date
2025-06-14
Authors
Wallace, Richard J.
Freuder, Eugene C.
Journal Title
Journal ISSN
Volume Title
Publisher
Taylor & Francis
Published Version
Abstract
Problem simplification is of continuing interest in the field of constraint satisfaction. In this paper we examine properties associated with the basic idea of value substitutability and show how certain forms of substitutability can be organised into a strict hierarchy. One of these properties, here called replaceability, has been identified by other authors as being of special interest. We confirm these claims by showing that replaceability is the most general property in this hierarchy that allows local to global inferences. We introduce new algorithms for establishing local (neighbourhood) replaceability that are superior to other types of algorithms designed for this task and demonstrate their effectiveness (values removed) for a variety of constraint types. We show that it is sometimes possible to infer replaceability, leading to appreciable reductions in time required to reduce a problem to irreplaceable domain sets. We also describe a new kind of complexity peak that occurs with neighbourhood replaceability algorithms and analyse this effect.
Description
Keywords
Constraint satisfaction , Substitutability , Replaceability , Problem reformulation
Citation
Wallace, R. J. and Freuder, E. C. (2025) 'Replaceability and a simple substitutability hierarchy for constraint satisfaction problems', Journal of Experimental & Theoretical Artificial Intelligence, pp.1-48. https://doi.org/10.1080/0952813X.2025.2509181
Link to publisher’s version
Copyright
© 2025, Informa UK Limited, trading as Taylor & Francis Group. This is an Accepted Manuscript of an item published by Taylor & Francis in Journal of Experimental & Theoretical Artificial Intelligence on 14 June 2025, available online: https://doi.org/10.1080/0952813X.2025.250918