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 featureterm logic, l l o X F ' 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. .
