Studies in incremental natural-language analysis

Abstract: "This thesis explores the problem of incremental analysis of natural-language text. Incrementality can be motivated on psychological grounds, but is becoming increasingly important from an engineering perspective as well. A major reason for this is the growing importance of highly interactive, 'immediate' and real-time systems, in which sequences of small changes must be handled efficiently. The main technical contribution of the thesis is an incremental parsing algorithm that analyses arbitrary changes (insertions, deletions and replacements) of a text. The algorithm is grounded in a general chart-parsing architecture, which allows different control strategies and grammar formalisms to be used. The basic idea is to analyse changes by keeping track of dependencies between partial analyses (chart edges) of the text. The algorithm has also been adapted to interactive processing under a text editor, thus providing a system that parses a text simultaneously as it is entered and edited. By adopting a compositional and dynamic model of semantics, the framework can be extended to incremental interpretation, both with respect to a discourse context (induced by a connected, multisentential text) and a non-linguistic context (induced by a model of the world). The notion of keeping track of dependencies between partial analyses is similar to reason maintenance, in which dependencies are used as a basis for (incremental) handling of belief changes. The connections with this area and prospects for cross-fertilization are discussed. In particular, chart parsing with dependencies is closely related to assumption-based reason maintenance. Both of these frameworks allow competing analyses to be developed in parallel. It is argued that for the purpose of natural-language analysis, they are superior to previously proposed, justification-based approaches, in which only a single, consistent analysis can be handled at a time."