Matching in Description Logics with Existential Restrictions
Franz Baader, R. Kuesters · 1999
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 polynomialtime 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. 1 Motivation Matching concepts against patterns is a relatively new inference problem for DLs, which has been introduced in [5, 7] to support the pr...