We are using a special representation for complex constraints, called matrix notation (see also [VanNoord1993]). In order to distinguish variable names from features and constants we adopt the Prolog convention that only variable names start with a capitalized letter and names of features or constants have to be written in lower case. For example the following constraints on the variable
are represented in matrix notation as follows (the variables and are computed during the computation of the basic constraint):
If variables occur only once in a matrix they are omitted. This is the case for the above example, so that it will also be written as:
Furthermore, empty feature structures will not been shown explicitly, i.e.,
is written as
For feature structures encoding lists I will adopt the list notation from [Pollard and Sag1987]. The feature structure encoding of the following list
will be written more readable using angled brackets
The empty list then will be written as
We will also make use of the head/tail representation of lists known from Prolog. Thus to explicitly represent the first element of a list from the rest we write
thus, for instance, a, b, c can also be written as a|< b, c>.
The difference list of the feature structure
will be written as
The empty difference list will be written as