User Tools

Site Tools


Matching Concept Descriptions with Existential Restrictions Revisited (BibTeX)

@TECHREPORT{BaaderKuesters-LTCS-99-13-1999,
  author = {F.~Baader and R.~K{\"u}sters},
  title = {Matching Concept Descriptions with Existential Restrictions Revisited},
  institution = {LuFG Theoretical Computer Science, RWTH Aachen},
  year = 1999,
  type = {LTCS-Report},
  number = {LTCS-99-13},
  address = {Germany},
  note = {See \url{http://www.informatik.rwth-aachen.de/Forschung/aib.php}.},
  abstract = {Matching of concepts against patterns is a  new inference task in Description Logics, which was  originally motivated by applications of the Classic system. Consequently, the work on this problem was until now mostly concerned with sublanguages of the  Classic language, which does not allow for  existential restrictions.  Motivated by an application in chemical process engineering, which requires a description language with existential restrictions, this paper investigates the matching problem in Description Logics with existential restrictions. It turns out that existential restrictions make matching more  complex in two respects. First, whereas matching in sublanguages  of Classic is polynomial, deciding the existence of  matchers is an NP-complete problem in the presence of existential  restrictions. Second, whereas in sublanguages of Classic solvable matching problems have a unique least matcher, this is not the case  for languages with existential restrictions.  Thus, it is not a priori  clear which of the (possibly infinitely many) matchers should be  returned by a matching algorithm.  After determining the complexity of the decision problem, the present paper first investigates the question of what are  "interesting" sets of matchers, and then describes algorithms for computing these sets for the languages EL (which allows for conjunction and existential restrictions) and ALE.}
}