In this chapter we have introduced constraint-based grammars as an appropriate means for specifying reversible grammars. We have introduced the constraint logic programming scheme of [Höhfeld and Smolka1988] as an appropriate formal means for representing constraint-based grammars, which also provides an operational semantics in the form of generalized SLD-resolution. Following the constraint-based grammar formalism introduced in [VanNoord1993] we have shown how to specify constraint-based grammars by basically specifying the manner of representing phonological and semantic information.
Although we have chosen a simple constraint language in order to highlight the new results in a clean but simple way, the generalization of Höhfeld and Smolka's scheme will guarantee that the results of this thesis also carries over for more complex constraint languages.
At this place we want to emphasize, that we had consciously used well-known and accepted formalisms rather than defining our own formalism. The main reason is that we are interested in the application of constraint-based formalisms for natural language processing. Thus our focus of attention is algorithmic rather than theoretical. However, basing it on accepted theoretical approaches makes our project an attractive and worthwhile venture. We start doing this by presenting an efficient uniform tabular algorithm for parsing and generation of constraint-based grammars.