7 Solver

This chapter presents the heart of the XDG development kit, viz. the XDK solver, a solver for specialized constraint satisfaction problems (CSPs). These CSPs are defined by:

1. a list of tokens that we call words
2. the lexicon which maps each word to a set of possible lexical entries.
3. the set of used dimensions and the set of principles used on them

The CSP is split up into a set of dimensions, each of which uses a set of principles.

The principles are either taken from a predefined principle library, or can be conveniently written in a First-Order Logic using the principle compiler PrincipleWriter.

A principle definition includes:

• the principle identifier
• the set of dimension variables
• the set of argument variables and their types
• default values for the argument variables
• the type of the model record introduced by the principle
• the set of constraints and their priorities which implement the principle. The higher the priority, the earlier the constraint is executed by the solver. By convention, node constraints have priority >=100 for constraints doing propagation, and <100 for those doing distribution.

We give an overview of the library in Principle overview (Principles overview). In Principle list (Principles list), we explain the whole range of principles in the current library.

Developers only: The node record is the internal representation of a node in a solution. We explicate it in Node record. In Writing new principles we explain how to write new principles.

• Principles overview: Principles overview
• Principles list: Principles list

-- developers only --

• Node record: Node record
• Writing new principles: Writing new principles