Feature Logic With Weak Subsumption Constraints

FEATURE LOGIC WITH WEAK SUBSUMPTION CONSTRAINTS Jochen Dbere IBM Deutschland OmbH Science Center - IKBS P.O. Box 80 08 80 D-7000 Stuttgart 80, Germany ABSTRACT In the general framework of a constraint-based grammar formalism often some sort of feature logic serves as the constraint language to de- scribe linguistic objects. We investigate the ex- tension of basic feature logic with subsumption (or matching) constraints, based on a weak no- tion of subsumption. This mechanism of one- way information flow is generally deemed to be necessary to give linguistically satisfactory de- scriptions of coordination phenomena in such formalisms. We show that the problem whether a set of constraints is satisfiable in this logic is decidable in polynomial time and give a solution algorithm. 1 Introduction Many of the current constralnt-based grammar formalisms, as e.g. FUG [Kay 79, Kay 85], LFG [Kaplan/Bresnan 82], HPSG [Pollard/Sag 87], PATR-II [Shieber et al. 83] and its derivates, model linguistic knowledge in recursive fea- ture structures. Feature (or functional) equa- tions, as in LFG, or feature terms, as in FUG or STUF [Bouma et al. 88], are used as con- straints to describe declaratively what proper- ties should be assigned to a linguistic entity. In the last few years, the study of the for- real semantics and formal properties of logics involving such constraints has made substan- tial progress [Kasper/Rounds 86, Johnson 87, Smolka 88, Smolka 89], e.g., by making precise which sublanguages of predicate logic it corre- sponds to. This paves the way not only for reli- able implementations of these formalisms, but also for extensions of the basic logic with a precisely defined meaning. The extension we present here, weak subsumption constraints, is a mechanism of one-way information flow, often proposed for a logical treatment of coordination in a feature-based unification grammar. 1 It can I Another application would be type inference in a grammar formalism (or programming language) that be informally described as a device, which en- ables us to require that one part of a (solution) feature structure has to be subsumed (be an in- stance of) another part. Consider the following example of a coordina- tion with "and", taken from [Shieber 89]. (1) Pat hired [tcP a Republican] and [NP a banker]. (2) *Pat hired [NP a Republican] and lAP proud of it]. Clearly (2) is ungrammatical since the verb "hire" requires a noun phrase as object com- plement and this requirement has to be ful- filled by both coordinated complements. This subcategorization requirement is modeled in a unification-based grammar generaUy using equations which cause the features of a comple- ment (or parts thereof encoding the type) to get unified with features encoding the requirements of the respective position in the subcategoriza- tion frame of the verb. Thus we could assume that for a coordination the type-encoding fea- tures of each element have to be "unified into" the respective position in the subcategorisation frame. This entails that the coordinated ele- ments are taken to be of one single type, which then …

Content truncated to 500 words