M. de Rijke
- Constraint methods for modal satisfiability
- Book title
- Recent advances in constraints: Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Solving and Constraint Logic Programming Cork, CSCLP 2003, Budapest, Hungary, June 30- July 2, 2003: selected papers
- Pages (from-to)
- Berlin: Springer
- Lecture notes in computer science
- Volume | Edition (Serie)
- Document type
- Faculty of Science (FNWI)
- Informatics Institute (IVI)
Modal and modal-like formalisms such as temporal or description logics go beyond propositional logic by introducing operators that allow for a guarded form of quantication over states or paths of transition systems. Thus, they are more expressive than propositional logic, yet computationally better behaved than rst-order logic. We propose constraint-based methods to model and solve modal satisability problems. We model the satisability of basic modal formulas via appropriate sets of nite constraint satisfaction problems, and then resolve these via constraint solvers. The domains of the constraint satisfaction problems contain other values than just the Boolean 0 or 1; for these values, we create specialised constraints that help us steer the decision procedure and so keep the modal search tree as small as possible. We show experimentally that this constraint modelling gives us a better control over the decision procedure than existing SAT-based models.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.