In Chapter 2 we summarize the most important arguments for reversible natural language processing and discuss the state of the art in the area of grammar reversibility. We present a classification scheme for reversible systems and apply this scheme in the discussion of current approaches in grammar reversibility.
In Chapter 3 we present the formal and linguistic foundations on which this thesis is based. We first introduce constraint-based grammar theories as appropriate means for specifying reversible grammars. In these theories, the grammatical well-formedness of possible utterances is described in terms of identity constraints a linguistic structure must fulfill taking into account information of different strata (e.g., phonology, syntax and semantics) in a uniform and completely declarative way, e.g., Lexical Functional Grammar (LFG, [Bresnan1982]), Head-Driven Phrase Structure Grammar (HPSG, [Pollard and Sag1987]) and constraint-based categorial frameworks (cf. [Uszkoreit1986a] and [Zeevat et al.1987]).
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.
The computational framework of our approach is based on constraint logic programming (CLP). CLP combines very well with the constraint-based view on grammar theories as well as with the deductive view of language processing, where parsing and generation are uniformly considered as proof strategies (cf. [Pereira and Warren1983], [Shieber1988] and chapter 4 of this thesis). Moreover, we show in this thesis how a tight integration of parsing and generation can be realized using CLP in an elegant and efficient way.
These aspects together makes CLP an excellent platform for combining methods from Computational Linguistics and Artificial Intelligence and hence for achieving theoretically sound and practical natural language systems.
In Chapter 4 we present the uniform algorithm. We first briefly introduce the Earley deduction framework introduced in [Pereira and Warren1983]. We then present a first version of the uniform tabular algorithm that makes use of a data-driven selection function, and show how it is augmented by a flexible agenda-based control regime. After illustrating how the algorithm performs parsing and generation, we extend this first version so that it can maintain structured item sets efficiently. We present a uniform indexing mechanism that can be used in the same manner for both parsing and generation. However, since we use the current portion of the input for determining the ``content'' of internal item sets, the item sets are ordered according to the actual structure of the input. The effect is that produced items are split into equivalence classes. The individual classes are connected by means of backward pointers, so that each item can directly be restricted to those items that belong to a particular equivalence class.
This uniform indexing mechanism is the basis of the item sharing approach whose specification is also given in that chapter. The item sharing approach is realized as an object-oriented extension of the uniform algorithm which allows us to handle different agendas and hence individual priority functions for parsing and generation.
In Chapter 5 we present a linguistic performance model which is based on the new uniform processing model and which takes full advantage of the item sharing method. We first discuss the uniform grammatical model as an integral part of a natural language system and its implications of the system's design. On the basis of this discussion we present a fundamental generation strategy, namely that of avoiding ambiguous output. The idea here is that the generator runs its output back through the understanding system to make sure it's unambiguous. The most advanced technology we are presenting is a chart-based incremental generate-parse-revise strategy. During natural language generation computed partial strings are parsed in order to test whether the partial string just produced can cause misunderstandings. If this is the case this partial string is rejected and another alternative is determined. This part of the process is called revision, where the parser performs the task of monitoring the generator's process.
We also apply this method during the understanding mode of a natural language system for the purpose of disambiguation by means of the generation of paraphrases. The idea here is that after parsing an utterance, then if this utterance is ambiguous leading to several readings, corresponding paraphrases are generated, that reflect the semantic differences. The user is then asked to choose the one he intended.
These novel techniques are realized as direct extensions of the uniform tabular algorithm, taking full advantage of the item sharing method. Thus, we are able to show that our novel approach to uniform processing leads to efficient and practical interleaving of generation and parsing.
In Chapter 6 we summarize and discuss the basic results of the thesis and outline some important future directions.