Logic in Computer Science (LICS 1990)

Paper: On subsumption and semiunification in feature algebras (at LICS 1990)

Authors: Dorre, J. Rounds, W.C.

Abstract

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

BibTeX

  @InProceedings{DorreRounds-Onsubsumptionandsem,
    author = 	 {Dorre, J. and Rounds, W.C.},
    title = 	 {On subsumption and semiunification in feature algebras},
    booktitle =  {Proceedings of the Fifth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1990},
    year =	 1990,
    editor =	 {John Mitchell},
    month =	 {June}, 
    pages =      {300--310},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }