User Tools

Site Tools

Unification in a Description Logic with Transitive Closure of Roles (BibTeX)

  author = {F.~Baader and R.~K{\"u}sters},
  title = {Unification in a Description Logic with Transitive Closure of Roles},
  booktitle = {Proceedings of the International Workshop on Description Logics 2001 (DL 2001)},
  year = 2001,
  editor = {D.L.~McGuinness and P.F.~Patel-Schneider and C.~Goble and R.~M{\"o}ller},
  note = {Proceedings online available from \url{http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/}},
  address = {Stanford University, CA},
  abstract = {Unification of concept descriptions was introduced by Baader and Narendran as a tool for detecting redundancies in knowledge bases. It was shown that unification in the small description logic  FL0,  which allows for conjunction, value restriction, and the top concept only, is already ExpTime complete. The present paper shows that the complexity does not increase if one additionally allows for composition, union, and transitive closure of roles. It also shows that matching (which is polynomial in FL0) is PSpace-complete in the extended description logic.}