When Functional and Bijective Constraints Make a CSP Polynomial
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction Problems. Pages 224-230.
Abstract
Many works have been carried out to improve search efficiency in CSPs, but few of them treated the semantics of the constraints. In this paper, we expose some properties of two classes of constraints, functional and bijective constraints: we first present conditions under which arc and path consistencies are sufficient to guarantee the existence of a bactrack free solution; we then exhibit classes of polynomial problems, and finally we propose a new method of decomposition for problems containing functional or bijective constraints. An interesting point in this method is that th e resolution complexity is known prior to the search.
@inproceedings{ijcai1993p32,
title = {When Functional and Bijective Constraints Make a CSP Polynomial},
author = {David, Philippe},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {224--230},
year = {1993},
note = {Constraint Satisfaction Problems},
url = {https://ijcai.org/proceedings/1993/32},
}
TY - CPAPER TI - When Functional and Bijective Constraints Make a CSP Polynomial AU - David, Philippe T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 224 EP - 230 UR - https://ijcai.org/proceedings/1993/32 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
