Replaceability and a simple substitutability hierarchy for constraint satisfaction problems
| dc.check.date | 2026-06-14 | en |
| dc.check.info | Access to this article is restricted until 12 months after publication by request of the publisher | en |
| dc.contributor.author | Wallace, Richard J. | en |
| dc.contributor.author | Freuder, Eugene C. | en |
| dc.contributor.funder | Science Foundation Ireland | en |
| dc.contributor.funder | European Regional Development Fund | en |
| dc.date.accessioned | 2025-07-15T12:46:05Z | |
| dc.date.available | 2025-07-15T12:46:05Z | |
| dc.date.issued | 2025-06-14 | en |
| dc.description.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. | en |
| dc.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.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 | en |
| dc.identifier.doi | 10.1080/0952813x.2025.2509181 | en |
| dc.identifier.eissn | 1362-3079 | en |
| dc.identifier.endpage | 48 | en |
| dc.identifier.issn | 0952-813X | en |
| dc.identifier.journaltitle | Journal of Experimental & Theoretical Artificial Intelligence | en |
| dc.identifier.startpage | 1 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/17704 | |
| dc.language.iso | en | en |
| dc.publisher | Taylor & Francis | en |
| dc.relation.ispartof | Journal of Experimental & Theoretical Artificial Intelligence | en |
| dc.relation.project | info:eu-repo/grantAgreement/SFI/Research Centres Programme/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ | en |
| dc.relation.project | info:eu-repo/grantAgreement/SFI/Principal Investigator Programme/05/IN/I886/IE/Employing Artificial Intelligence to Make Constraint Programming Easier to Use for Decision Making/ | en |
| dc.rights | © 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 | en |
| dc.subject | Constraint satisfaction | en |
| dc.subject | Substitutability | en |
| dc.subject | Replaceability | en |
| dc.subject | Problem reformulation | en |
| dc.title | Replaceability and a simple substitutability hierarchy for constraint satisfaction problems | en |
| dc.type | Article (peer-reviewed) | en |
| dc.type | journal-article | en |
