Horn extended feature structures
Stephen J. Hegner · 1991
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 Horn clauses in feature-term logic. HoXF's greatly generalize ordinary feature structures in admitting explicit representation of negative and implicational constraints. In contradistinction to the general case in which arbitrary logical constraints are allowed (for which the best known algorithms are exponential), there is a highly tractable algorithm for the unification of HoXF's.