Disjunctions and Inheritance in the Context Feature Structure System

Disjunctions and Inheritance in the Context Feature Structure System Martin BSttcher GMD-IPSI Dolivostra~e 15 D 6100 Darmstadt Germany boettche~darmstadt.gmd.de Abstract Substantial efforts have been made in or- der to cope with disjunctions in constraint based grammar formalisms (e.g. [Kasper, 1987; Maxwell and Kaplan, 1991; DSrre and Eisele, 1990].). This paper describes the roles of disjunctions and inheritance in the use of feature structures and their formal semantics. With the notion of contexts we abstract from the graph structure of feature structures and properly define the search space of alternatives. The graph unifica- tion algorithm precomputes nogood combi- nations, and a specialized search procedure which we propose here uses them as a con- trolling factor in order to delay decisions as long as there is no logical necessity for de- ciding. 1 Introduction The Context Feature Structure System (CFS) [BSttcher and KSnyves-Tdth, 1992] is a unification based system which evaluates feature structures with distributed disjunctions and dynamically definable types for structure inheritance. CFS is currently used to develop and to test a dependency grammar for German in the text analysis project KONTEXT. In this paper disjunctions and inheritance will be in- vestigated with regard to both, their application di- mension and their efficient computational treatment. The unification algorithm of CFS and the con- cept of virtual agreements for structure sharing has been introduced in [BSttcher and KSnyves-TSth, 1992]. The algorithm handles structure inheritance by structure sharing and constraint sharing which avoids copying of path structures and constraints completely. Disjunctions are evaluated concurrently without backtracking and without combinatoric mul- tiplication of the path structure. For that purpose the path structure is separated from the structure of disjunctions by the introduction of contexts. Contexts are one of the key concepts for main- taining disjunctions in feature terms. They describe readings of disjunctive feature structures. We define them slightly different from the definitions in [DSrre and Eisele, 1990] and [Backofen et ai., 1991], with a technical granularity which is more appropriate for their efficient treatment. The CFS unification algo- rithm computes a set of nogood contexts for all con- flicts which occur during unification of structures. An algorithm for contexts which computes from a set of nogoods whether a structure is valid, will be described in this paper. It is a specialized search procedure which avoids the investigation of the full search space of contexts by clustering disjunctions. We start with some examples how disjunctions and inheritance are used in the CFS environment. Then contexts are formally defined on the basis of the se- mantics of CFS feature structures. Finally the algo- rithm computing validity of contexts is outlined. 2 The Use of Disjunctions and Inheritance Disjunctions Disjunctions are used to express ambiguity and ca- pability. A first example is provided by the lexicon entry for German die (the, that, ...) in Figure 1. It may be nominative or accusative, and if it is singular the gender has to be feminine. Those parts of the term which are not inside a dis- junction are …

Content truncated to 500 words