Structure of the Thesis

The rest of this thesis is structured as follows:

Chapter 2: Typed Feature Structures

presents a short introduction to typed feature logic. The main notations and definitions are outlined, while several useful extensions are introduced.

Chapter 3: Unification-Based Grammars

an important grammatical formalism, Head-driven Phrase Structure Grammars, belonging to the class of unification-based grammars is presented here. Implementational aspects particular to Typed Feature Structure Grammars are also outlined. A new classification of the instances of variables used in TFSGs is introduced.

Chapter 4: Indexing for TFSG Parsing

presents the general problem of parsing with TFSGs, the motivation and details of indexing the chart for such grammars. A general indexing strategy suitable for chart-based parsers is introduced. The chapter concludes with a review of existing techniques that are similar to the proposed indexing method, discussing about the differences between filtering (as done by the existing methods) and indexing, as well as between statistical and non-statistical approaches, are discussed.

Chapter 5: Indexing for Non-Parsing Applications

investigates the current indexing research in related areas, such as information retrieval and lexicon indexing for generation. An overview of indexing for automated reasoning and databases is also presented.

Chapter 6: TFSG Indexing through Static Analysis

is the core chapter of this thesis. It introduces a simple indexing method (positional indexing), followed by the presentation of the theoretical foundations for our static analysis of grammar rules. A complete indexing strategy based on the static analysis is then introduced. The chapter concludes with the presentation of a practical indexing scheme (path indexing) derived from the static analysis.

Chapter 7: Experimental Evaluation

presents a preliminary evaluation of the indexing methods proposed in this thesis using a wide-coverage TFSG, followed by an investigation of the applicability of the proposed indexing methods to non-TFS grammar formalisms.

Chapter 8: Conclusions and Future Work

outlines the main achievements and proposes directions for future work.