User Tools

Site Tools

Matching in Description Logics with Existential Restrictions (BibTeX)

  author      = {F.~Baader and R.~K{\"u}sters},
  title       = {Matching in Description Logics with Existential Restrictions},
  booktitle   = {Proceedings of the International Workshop on Description Logics 1999 (DL'99)},
  year        = 1999,
  series      = {CEUR-WS},
  number      = 22,
  editor      = {P.~Lambrix and A.~Borgida and M.~Lenzerini and R.~M{\"o}ller and P.~Patel-Schneider},
  note        = {Proceedings online available from \url{http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-22/}},
  publisher   = {Link{\"o}ping University},
  ccl         = {yes},
  address     = {Sweden},
  abstract    = {Matching of concepts with variables (concept patterns) is a relatively new operation that has been introduced in the context of description logics, originally to help filter out unimportant aspects of large concepts appearing in industrial-strength knowledge bases. Previous work on this problem has produced polynomial-time matching algorithms for sublanguages of the DL used in CLASSIC. Consequently, these algorithms cannot handle existential restrictions.  In this paper, we consider matching in DLs allowing for existential restrictions. We describe decision procedures that test solvability of matching problems as well as algorithms for computing complete sets of matchers. Unfortunately, these algorithms are no longer polynomial-time, even for the small language EL, which allows for the top concept, conjunction and existential restrictions.}