Since the last decade a family of linguistic theories known under the term constraint-based grammar theories play an important role within the field of natural language processing. One of the reasons for their importance is that they are declarative, i.e., are able to express grammatical knowledge without regard to any specific use. Since they also integrate information from different levels of linguistic description uniformly they are very well suited as the linguistic base of a reversible system. In this sense, constraint-based grammars are reversible.
The common design feature of these formalisms is that they model
linguistic entities (e.g., words and phrases) `` 
as partial
information structures, which mutually constrain possible collocations
of phonological structure, syntactic structure, semantic content, and
contextual factors in actual linguistic situations. Such objects are in
essence data structures which specify values for attributes; their
capability to bear information of non-trivial complexity arises from
their potential for recursive embedding (the value of some attribute may
be another information structure with internal structure of its own)
and structure-sharing (one and and the same structure may occur as the
value of distinct attributes in a larger structure)'' [Pollard and Sag1987],
page 7. Since, these informational structures are viewed as
partial, they are used to represent only necessary restrictions or
constraints of such properties a linguistic object must
fulfill; hence the name constraint-based theories. To give an example,
consider the following simplified attribute-value representation (also known as
feature structure) in the commonly used feature-matrix
notation, which is intended to represent the (partial) information
about the utterance ``peter cries'':
This structure expresses that the utterance ``peter cries'' is a linguistic object of class sentence, whose phonological representation is peter,cries, which has been formed from two objects, one for the utterance ``peter'' and one for ``cries'' and that the semantic content is the same as that of ``cries'' which by itself is built by combining the semantic structure of `cry' and `the-peter'. Clearly, this data structure is only a model of the `real' linguistic object. However, it characterizes relevant properties of the information the `real' object conveys.
The underlying assumption of all constraint-based theories is
that in the actual utterance situation the specification of linguistic objects
is built in a monotonic way independently of the specific processing task
at hand (e.g., parsing, generation) from different sources, including
lexicon and grammar rules, as well as from language universal and
language specific principles. Building larger objects from smaller ones
is assumed to be performed by some sort of constraint-solving whose
task is to collect all constraints of
the various attending objects, so that the resulting structure
describes a consistent, i.e., grammatical linguistic object.
Most important from a reversibility standpoint is that the theories only characterize what constraints are important during natural language use, not in what order they are applied. Thus they are purely declarative. Furthermore, since almost all theories assume that a natural language grammar not only describes the correct sentences of a language but also the semantic structure of grammatically well-formed sentences, they are perfectly well suited to a reversible system, because they are neutral with respect to interpretation and production.
In the last few years constraint-based formalisms have undergone a rigorous formal investigation (consider for example [Shieber1989, Smolka1988, Smolka1992]). This has led to a general characterization of constraint-based formalisms where feature structures are considered to constitute a semantic domain and constraints are considered syntactic representations of such `semantic structures'. This logical view has several advantages. On the one hand, it has been possible to properly incorporate concepts like disjunction or negation as part of the (syntactic) constraint language and to interpret them relative to a given domain of feature structures (usually defined as graph-like or tree-like structures). On the other hand it has been possible to combine constraint-based formalisms with logic programming, which fits into a new research area known under the term constraint logic programming (CLP) [Jaffar and Lassez1987]. This enables us to extend the view of natural language as deduction for essentially arbitrary constraint-based formalisms.
A general characterization of constraint logic programming is given in [Höhfeld and Smolka1988]. They show that the nice properties of logic programs extend to definite clause specifications over arbitrary constraint languages.
We will use the scheme of [Höhfeld and Smolka1988] as our underlying formal language. We therefore first summarize the most important definitions and statements given there. We then specify a concrete constraint language also called which is based on the definitions of [Smolka1992] and [VanNoord1993]. This constraint language will be used as the central data structure for representing linguistic objects. The relational extensions provided by then serve as the basis for representing grammatical rules, i.e., complex compositional entities. The use of the presented formalism in writing grammars is illustrated in section 3.3.