M.Sc. Thesis

"Logic Programming Models for Parallel Parsing in Natural Language"


The focus of this thesis is the parallel processing of natural language The investigation is made from a Logic Programming (LP) perspective, motivated by the lack of commitment to sequentiality of more conventional programming paradigms and languages, since, theoretically, the logic of the program and the control of its execution are "separated". The focus is on the syntactic aspect of natural language processing, on written language, and restricted to the scope of the sentence.

The forms of parallelism present in logic programs are described, using the AND/OR process model as the basic framework, together with a summary of the general problems involved with parallel processing, and previous theoretical results of parallel parsing of formal languages. language. The linguistic focus in the thesis is on Logic Grammars. The inherent possibilities for parallel processing in Natural Langauge Processing (NLP) are assessed and a critical analysis of existing parallel parsing systems for NLP is given. Consideration is given to the impact of both the underlying grammatical model and the parallel architecture on the type and scope of parallelism achieved.

The linguistic problem of word order is used as a "real" problem that illustrates both the complexity of natural language and the variation across languages that any substantial NLP system must be able to handle. A parallel approach to the problem of word order seems a natural one, given the initial postulate that a freer word order may mean that a word or phrase in a sentence is less dependent on its position for its meaning and various constituents of a sentence may be more independent and amenable to a parallel treatment. We extend our analysis of existing parallel parsing systems to consider how they might handle this problem of word order. We assess how the performance of the system is affected when the language used has fewer constraints on word order. We then extend our search for possible solutions: we give a critical analysis of research on parsing free word order languages and assess their potential for parallel treatment.

The major contribution of this thesis is a detailed investigation of the diverse and complex issues involved in developing logic programming models for parallel parsing in natural language and our critical analysis of existing relevant research. However ideas that arise from this analysis and the subsequent identification of inadequacies in existing approaches are developed. These ideas range from problems related purely to parallel parsing, such as the construction of a top-down parser in stream AND-parallel LP code and further discussion of the question of parallel parsing, to the more specific problems involved with the question of word order, such as a scheme for specifying Logic Rules for a parallel LP parser that allows us to handle variation in degree of word order and further suggestions for handling discontinuities with a parallel parser.