World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Selected Papers from the 24th Annual IEEE International Conference on Tools with Artificial Intelligence (ICTAI-2012); Guest Editors: George A. Tsihrintzis, Themis Panayiotopoulos, Ioannis Vlahavas and Sotiris ZiavrasNo Access

Compiling CSPs: A Complexity Map of (Non-Deterministic) Multivalued Decision Diagrams

    https://doi.org/10.1142/S021821301460015XCited by:5 (Source: Crossref)

    Constraint Satisfaction Problems (CSPs) offer a powerful framework for representing a great variety of problems. The difficulty is that most of the requests associated with CSPs are NP-hard. When these requests have to be addressed online, Multivalued Decision Diagrams (MDDs) have been proposed as a way to compile CSPs.

    In the present paper, we draw a compilation map of MDDs, in the spirit of the NNF compilation map, analyzing MDDs according to their succinctness and to their tractable transformations and queries. Deterministic ordered MDDs are a generalization of ordered binary decision diagrams to non-Boolean domains: unsurprisingly, they have similar capabilities. More interestingly, our study puts forward the interest of non-deterministic ordered MDDs: when restricted to Boolean domains, they capture OBDDs and DNFs as proper subsets and have performances close to those of DNNFs. The comparison to classical, deterministic MDDs shows that relaxing the determinism requirement leads to an increase in succinctness and allows more transformations to be satisfied in polynomial time (typically, the disjunctive ones). Experiments on random problems confirm the gain in succinctness.

    This is a revised, detailed version of the eponymous paper published in the Proceedings of the 24th International Conference on Tools with Artificial Intelligence (ICTAI 2012). Note that this revision features a change in terminology, saving the name “MDD” for syntactically deterministic structures, and introducing a dedicated name for non-deterministic ones.