Constrained Decision Diagrams

Abstract

A general n-ary constraint is usually represented explicitly as a set of its solution tuples, which may need exponential space. In this paper, we introduce a new representation for general n-ary constraints called Constrained Decision Di-agram (CDD). CDD generalizes BDD-style representations and the main feature is that it combines constraint reason-ing/consistency techniques with a compact data structure. We present an application of CDD for recording all solutions of a conjunction of constraints. Instead of an explicit represen-tation, we can implicitly encode the solutions by means of constraint propagation. Our experiments confirm the scala-bility and demonstrate that CDDs can drastically reduce the space needed over explicit and ZBDD representations.