Matching Concept Descriptions with Existential Restrictions Revisited

Franz BaaderFranz Baader, R. KüstersR. Küsters

Datei:BaaderKuesters-LTCS-99-13-1999.ps.gz

Download

Franz Baader, R. Küsters
Matching Concept Descriptions with Existential Restrictions Revisited
Technical Report, LuFG Theoretical Computer Science, RWTH Aachen, volume LTCS-99-13, 1999. LTCS-Report

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: See http://www-lti.informatik.rwth-aachen.de/Forschung/Reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ BaaderKuesters-LTCS-99-13-1999,
  address = {Germany},
  author = {F. {Baader} and R. {K{\"u}sters}},
  institution = {LuFG Theoretical Computer Science, RWTH Aachen},
  note = {See http://www-lti.informatik.rwth-aachen.de/Forschung/Reports.html.},
  number = {LTCS-99-13},
  title = {Matching Concept Descriptions with Existential Restrictions Revisited},
  type = {LTCS-Report},
  year = {1999},
}