A Language for the Statement of Binary Relations over Feature Structures

A Language for the Statement of Binary Relations over Feature Structures Graham Russell Afzal Ballim Dominique Estival Susan Warwick-Armstrong ISSCO, 54 rte. des Acacias 1227 Geneva, Switzerland elu@divsun.unige.ch Abstract Unification is often the appropriate method for expressing relations between representations in the form of feature structures; however, there are circumstances in which a different approach is desirable. A declarative formalism is presented which permits direct mappings of one feature structure into another, and illustra- tive examples are given of its application to areas of current interest. 1. Introduction Benefits arising from the adoption of unification as a tool in computational linguis- tics are well known: a declarative, monotonic method of combining partial information expressed in data structures convenient for linguistic applications permits the writing of sensible grammars that can be made indepen- dent from processing mechanisms, and a grow- ing familiarity, in both theoretical and compu- tational circles, with the techniques of unification fosters fruitful interchange of ideas and experiences. There are, however, occa- sions when unification alone is not an appropriate tool. In essence, unification is a ternary relation in which two structures, when merged, form a third; it is less attractive in cir- cumstances where the relation to be expressed is binary - when one would like to manipulate a single feature structure (FS), perhaps simu- lating the direct transformation of one FS into another. 1 The present paper introduces a declarative formalism intended for the expres- sion of such relations, and shows how it may be applied to some areas of current interest. The formalism in question is based upon a notion of 'transfer rule'; informally, a set of such rules may be considered as characterizing We are indebted to Jacques Jayez for comments on an earlier draft of this paper. 1 Clearly there is a sense in which such relations can be viewed as ternary: T(FI, R, F2), where 171 and 172 are • 17Ss, and R is the rule set which relates them. a binary relation over a set of feature struc- tures, the properties of that relation depending on the content of the particular rule set in use. Transfer rules associate the analysis of one FS with the synthesis of another; they may be thought of as a specialized variety of pattern- matching rule. They are local in nature, and permit the recursive analysis and synthesis of complex structures according to patterns specified in a format closely related to that widely employed in unification-based compu- tational linguistics. Indeed, the interpretation of transfer rules involves unification, albeit in a context which restricts it to the role of a structure-building operation. 2 In the remainder of this paper we provide a brief specification of the transfer rule formal- ism, discuss its interpretation, outline two alternative rule application regimes, and illus- trate the use of the formalism in the areas of machine translation and reduction of FSs to canonical form. We conclude with an over- view of continuing strands of research. 2. Rule Format and Interpretation 2.1. …

Content truncated to 500 words