An interpretation
of
consists of a domain
*D*^{} which is the set of all feature graphs built from *L*, *C* and *V*,
and a solution mapping
^{ . } which will be defined below.
An -assignment is a mapping from the set of variables to
*D*^{}. I write
*ASS*^{} for the set of all
-assignments. Variables and constants will denote feature graphs,
relative to some assignment.

The denotation of a variable
X w.r.t. assignment
is
simply
(X). The denotation of a constant
c is the
feature graph
(c,) (for any assignment). The denotation of
a descriptor *sp* is defined as *F*^{p} where *F* is the
denotation of *s*; i.e. the denotation of *sp* is the subgraph
at *p* of the graph denoted by *s*. Note that the denotation of some
descriptors is undefined. Summarizing:

As an example, consider the feature graph *F*_{2} in figure 2.2.

An interpretation
*satisfies* an atomic constraint
= *d*_{1}
*d*_{2}, relative to an assignment , written
if the denotation of descriptors *d*_{1}, *d*_{2}
are both defined and the same, i.e.:

Hence,
satisfies the equation
*X**l*_{1}*l*_{3}
*X**l*_{2}*l*_{3} with respect to the assignment that maps *X* to
the feature graph *F*_{2} defined above. As another example,
also satisfies the equation
*X**l*_{1}*l*_{3}*l*_{1}
c_{2}, with the same .

The *solutions* of a constraint are all assignments that give
satisfaction. Constraints are thus seen as restrictions on the values
the variables in the constraints can take. The solutions of an atomic
constraint
are defined as follows:

The set of solutions of a constraint
,...,
is defined as
the intersection of the solutions of its atomic constraints:

(,...)^{} = _{def}

A constraint is *satisfiable* iff it has at least one solution.
Two constraints are *equivalent* iff they have the same solutions.
A constraint is *valid* iff its solutions are all possible
assignments
*ASS*^{}.

1998-09-30