The Range and Roots Constraints: Specifying Counting and Occurrence Problems
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 60-64.
Abstract
We propose a simple declarative language for specifying a wide range of counting and occurrence constraints. This specification language is executable since it immediately provides a polynomial propagation algorithm. To illustrate the capabilities of this language, we specify a dozen global constraints taken from the literature. We observe one of three outcomes: we achieve generalized arc-consistency; we do not achieve generalized arc-consistency, but achieving generalized arcconsistency is NP-hard; we do not achieve generalized arc-consistency, but specialized propagation algorithms can do so in polynomial time. Experiments demonstrate that this specification language is both efficient and effective in practice.
@inproceedings{ijcai2005p69,
title = {The Range and Roots Constraints: Specifying Counting and Occurrence Problems},
author = {Bessiere, Christian and Hebrard, Emmanuel and Hnich, Brahim and Kiziltan, Zeynep and Walsh, Toby},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {60--64},
year = {2005},
url = {https://ijcai.org/proceedings/2005/69},
}
TY - CPAPER TI - The Range and Roots Constraints: Specifying Counting and Occurrence Problems AU - Bessiere, Christian AU - Hebrard, Emmanuel AU - Hnich, Brahim AU - Kiziltan, Zeynep AU - Walsh, Toby T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 60 EP - 64 UR - https://ijcai.org/proceedings/2005/69 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
