4.1 Constraint Solving

When we deal with solving underspecified descriptions, the two algorithmic problems that concern us most are the following:

Satisfiability

Given a constraint graph, we need to decide whether there is a -structure into which it can be embedded.

Enumeration

Given a constraint graph, we have to compute all -structures into which it can be embedded.

These are the problems adressed in this section. The concept of a solved form will be central to the solutions that we develop.

• 4.1.1 Satisfiability and Enumeration

• 4.1.2 Solved Forms

• 4.1.3 Solved Forms: An Example

• 4.1.4 Defining Solved Forms