Constraint Solving over Semirings
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 624-629.
Abstract
We introduce a general framework for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated to each tuple of values of the variable domain, and the two semiring operations (+ and x) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that some conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving schemes, thus allowing one both to formally justify many informally taken choices in existing schemes, and to prove that the local consistency techniques can be used also in newly defined schemes.
@inproceedings{ijcai1995p82,
title = {Constraint Solving over Semirings},
author = {Bistarelli, Stefano and Montanari, Ugo and Rossi, Francesca},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {624--629},
year = {1995},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1995/82},
}
TY - CPAPER TI - Constraint Solving over Semirings AU - Bistarelli, Stefano AU - Montanari, Ugo AU - Rossi, Francesca T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 624 EP - 629 UR - https://ijcai.org/proceedings/1995/82 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
