---
title: "The Range and Roots Constraints: Specifying Counting and Occurrence Problems"
authors:
  - "Christian Bessière"
  - "Emmanuel Hebrard"
  - "Brahim Hnich"
  - "Zeynep Kiziltan"
  - "Toby Walsh"
doi: ""
url: "https://ijcai.org/proceedings/2005/69"
pdf: "https://ijcai.org/proceedings/2005/0069.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "60-64"
track: ""
keywords:
---

# The Range and Roots Constraints: Specifying Counting and Occurrence Problems

Christian Bessière, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh

*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.