On subsumption and semiunification in feature algebras

A generalization of term subsumption, or matching, to a class of mathematical structures called feature algebras is discussed. It is shown how these generalize both first-order terms and the feature structures used in computational linguistics. The notion of subsumption generalizes to a natural notion of homomorphism between elements of these algebras, and the authors characterize the notion, showing how it corresponds to a mapping which preserves partial information. In the setting of feature algebras, unification corresponds naturally to solving constraints involving equalities between strings of unary functions symbols, and semiunification also allows inequalities representing subsumption constraints. Their generalization allows the authors to show that the semiunification problem for finite feature algebras is undecidable. This implies that the corresponding problem for rational trees (cyclic terms) is also undecidable. Thus a partial solution to the decidability of this problem, which has been open for several years, is produced. >