A flexible unification formalism (FLUF)

Constraint-based grammar formalisms in their purest form use term or graph unification as the sole information-combining operation e.g. DCG or PATR-II. However, on descriptive grounds several extensions have been proposed, for example set values, negation, finite disjunction, infinite disjunctions expressed by regular paths (functional uncertainty), and generalization of feature structures. These extensions are intended to preserve the declarativity of the formalism and the monotonicity of unification. Other proposed extensions, such as defaults or multiple inheritance make the formalisms non-monotonic. Recent suggestions to control processing by means of annotations to rules make them non-declarative.

The increase of expressivity of constraint-based formalisms has, generally speaking, made them less tractable and less efficient for practical purposes. Since so many variants have been proposed, it has also become difficult to compare achievements and re-use resources that have been developed at different sites.

Lena Strömbäck has explored various possible and proposed extensions to constraint-based formalisms. In her licentiate thesis, Strömbäck (1992a), she surveys some of the recent systems and compares them in different respects, the most important being expressiveness, tractability, flexibility and predictability. While the first two are commonplace for representation languages, the other two are equally important. Flexibility means that it should be possible to vary and adjust the constructions provided by the system to the needs of a given application. Predictability means that the grammar writer should be able to predict the consequences on system behaviour when using the constructions allowed by the system for a certain purpose. Strömbäck notes that no existing system meets the demands on flexibility and proposes a framework that would make formalisms and systems better in this respect.

In more recent work, a formalism, FLUF, has been developed that is flexible in the desired sense, i.e. the user can define the constructs that he wants for a particular purpose, including feature structures, sets, lists and trees (Strömbäck, 1994a, 1994b, 1994c). The definitions of any construct can also be modified according to the user's needs. Multiple inheritance and non-monotonic constraints such as the constraints on coherence and completeness used in Lexical-Functional Grammars can also be defined. A prototype implementation of the system has been made, using narrowing to handle user-defined constructions (Hanus, 1994). While this makes the system inefficient for practical purposes, it is possible to improve the behaviour of the system by providing a library of special-purpose unifiers for those constructs that can be expected to be used often.

Back to Current Research