Studies in extended unification-based formalism for linguistic description : an algorithm for feature structures with disjunction and a proposal for flexible systems

Sammanfattning:

Unification-based formalisms have been used in computational and traditional linguistics for quite some while. In these formalisms the feature structure is the basic structure for representing linguistic information. However, these structures often do not suffice for describing linguistic phenomena and various extensions to the basic structures have been proposed. These extensions constitute the subject of this thesis.

The thesis contains a survey of the extensions proposed in the literature. The survey is concluded by stating the properties that are most important if we want to build a system that can handle as many of the extensions as possible. These properties are expressiveness, flexibility, efficiency and predictability. The thesis also evaluates four existing formalisms with respect to these properties. On the basis of the evaluation we also suggest how to design a system handling multiple extensions where the main emphasis have been laid on getting a flexible system.

As the main result the thesis specifies an algorithm for unifying disjunctive feature structures. Unlike previous algorithms, except Eisele & Dörre (1990), this algorithm is as fast as an algorithm without disjunction when disjunctions do not participate in the unification, it is also as fast as an algorithm handling only local disjunctions when there are only local disjunctions, and expensive only in the case of unifying full disjunction. By this behaviour the algorithm shows one way to avoid the problem that high expressiveness also gives low efficiency. The description is given in the framework of graph unification algorithms which makes it easy to implement as an extension of such an algorithm