Paper: Feature Logic With Weak Subsumption Constraints

ACL ID P91-1033
Title Feature Logic With Weak Subsumption Constraints
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1991

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.