Paper: Horn Extended Feature Structures: Fast Unification With Negation And Limited Disjunction

ACL ID E91-1007
Title Horn Extended Feature Structures: Fast Unification With Negation And Limited Disjunction
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1991
Authors

The notion of a Horn extended feature structure (HoXF) is introduced, which is a feature structure constrained so that its only allowable extensions are those satisfying some set of llorn clauses in feature- term logic, lloXF's greatly generalize ordinary fea- ture structures in admitting explicit representation of negative and implicational constraints. In contradis- tinction to the general case in which arbitrary logical constraints are allowed (for which the best known al- gorithms are exponential), there is a highly tractable algorithm for the unification of HoXF's. 1. PRELIMINARY CONCEPTS 1.1 Unification-based grammar formalisms Unification-based grammar formalisms constitute a cornerstone of many of the most important approaches to natural-language understanding (Shieber, 1986), (Col...