The grammar formalism I will define in this chapter is closely related to other formalisms currently in use in computational linguistics. These formalisms are known as `unification-based', `constraint-based', `information-based' and `feature-logic based'. Members of this class are for example Definite Clause Grammars , PATR II , Functional Unification Grammar  and formalisms underlying linguistic theories such as Generalized Phrase Structure Grammar , Lexical Functional Grammar , Unification Categorial Grammar , Categorial Unification Grammar  and Head-driven Phrase Structure Grammar .
A general characterization of such constraint-based formalisms is given in . They also show how the nice properties of logic programming languages carry over to a whole range of such constraint-based formalisms, by abstracting away from the actual constraint language that is used. I define such a constraint-based formalism in which the underlying constraint language, , consists of path equations. The most important characteristics of the formalism are:
Firstly, the principal `data-structures' of the formalism are feature structures, rather than first-order terms such as in Prolog. The motivation is that such feature structures are closer to the objects usually manipulated by linguists. Furthermore, in writing grammars the use of first-order terms becomes rather tiresome because it is necessary to keep track of the number of arguments functors take, and the position of sub-terms in such terms. Using path equations to define feature structures achieves some sort of data abstraction. As an example consider a program which manipulates terms such as the following
and suppose furthermore we want to refer to a specific part Cat of such a term T. In Prolog we are then forced to mention all intermediate functors, and for each functor we need to mention all its arguments (possibly using the `anonymous' variable `_'):
On the other hand, using path equations, it is possible to refer to such an embedded term by its path, in this case the value of Cat is obtained by the equation Cat T syn head cat.
This said, it should be stressed though that the difference between
the two approaches is not very decisive. In fact first-order terms may
be used in an implementation of such graph-based formalisms
, and data-abstraction can also be achieved by other
means such as syntactic macro's, or by auxiliary predicates.
From a linguistic point of view, the second characteristic is the most salient one. The formalism to be proposed, does not enforce that concatenation is the sole operation to combine strings. This choice can be motivated by:
If we do not incorporate a concatenative base, then we allow for investigation of other types of string combinations in natural language grammars. Several researchers, see for example , ,  and , have noted that analyses of a whole range of linguistic phenomena (most notably those involving discontinuous constituents) may be simplified by assuming other types of string operations. Some of the proposals are discussed in chapter 4.
As I will demonstrate below, if no assumptions about the construction of phonological representations, or semantic representations, are defined, then the parsing and generation problem of the formalism is generally not decidable. An important theme of this thesis is, to investigate parsing and generation procedures which can be applied usefully, for linguistically motivated grammars. In chapter 4 I describe a parsing algorithm for a subset of (), in which strings are constructed by operations which are to linear and non-erasing. This algorithm thus imposes some requirements on the ways strings are built, but these requirements are less restrictive than concatenation.
Another reason for developing a formalism which is not based on
concatenation is the observation that other (non-linguistic) problems
can be encoded in a unification-grammar as well, if we are not forced
to manipulate strings. In chapter 5 I show how the
resulting formalism can be used to define relationships between
language specific logical form encodings (chapter 5), as
the transfer component of a machine translation system. Furthermore,
the formalism is also used to define meta-interpreters in -- this
usage of the formalism also entails that no assumptions about string
construction are built-in.
The third characteristic states that the resulting formalism is a member of a class of constraint-based formalisms. Therefore, results that hold for this class carry over to the present formalism. In the other direction, it is easy to see how the current formalism can be extended to allow for other, perhaps more complex constraints. This is very useful as in the last few years a whole family of different constraints have been proposed that do extend formalisms such as PATR II. An overview of these proposals can be found in . The formalization of  makes it possible to see how these extended formalisms belong together. In a somewhat idealized view, parsing and generation algorithms defined for a member of the class of constraint-based formalisms, can be used for other members of this class, provided the appropriate constraint-solving techniques are available for the constraints incorporated in these other formalisms. For example, the generation- and parsing algorithms to be presented in the chapters 3 and 4, can easily be used for formalisms that include versions of negation and disjunction.