A fixpoint definition of dynamic constraint satisfaction

Timo Soininen, Esther Gelle, Ilkka Niemelä

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

    18 Citations (Scopus)

    Abstract

    Many combinatorial problems can be represented naturally as constraint satisfaction problems (CSP). However, in some domains the set of variables in a solution should change dynamically on the basis of assignments of values to variables. In this paper we argue that such dynamic constraint satisfaction problems (DCSP), introduced by Mittal and Falkenhainer, are more expressive than CSP in a knowledge representation sense. We then study the problem of generalizing the original DCSP with disjunctive activity constraints and default negation which are useful in, e.g., product configuration problems. The generalization is based on a novel definition of a solution to DCSP. It uses a fixpoint condition instead of the subset minimality condition in the original formulation. Our approach coincides with the original definition when disjunctions and default negations are not allowed. However, it leads to lower computational complexity than if the original definition were generalized similarly. In fact we show that the generalized DCSP is NP-complete. As a proof of concept, we briefly describe two novel implementations of the original DCSP and give test results for them.

    Original languageEnglish
    Title of host publicationPrinciples and Practice of Constraint Programming – CP’99
    Subtitle of host publication5th International Conference, CP’99, Alexandria, VA, USA, October 11-14, 1999. Proceedings
    EditorsJoxan Jaffar
    Place of PublicationBerlin
    Pages419-433
    Number of pages15
    ISBN (Electronic)978-3-540-48085-3
    DOIs
    Publication statusPublished - 1999
    MoE publication typeA4 Article in a conference publication
    EventInternational Conference on Principles and Practice of Constraint Programming - Alexandria, United States
    Duration: 11 Oct 199914 Oct 1999
    Conference number: 5

    Publication series

    NameLECTURE NOTES IN COMPUTER SCIENCE
    PublisherSPRINGER-VERLAG BERLIN
    Volume1713
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Conference on Principles and Practice of Constraint Programming
    Abbreviated titleCP
    CountryUnited States
    CityAlexandria
    Period11/10/199914/10/1999

    Keywords

    • CONFIGURATION

    Cite this