Matching in Description Logics with Existential Restrictions

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

Datei:BaaderKuesters-KR-2000.ps.gz

Download

Franz Baader, R. Küsters
Matching in Description Logics with Existential Restrictions
In A.G. Cohn and F. Giunchiglia and B. Selman, eds., Proceedings of the Seventh International Conference on Knowledge Representation and Reasoning (KR2000), 261-272, 2000. Morgan Kaufmann Publishers

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. This paper extends the existing work on matching in two directions. On the one hand, the question of what are the most ``interesting" solutions of matching problems is explored in more detail. On the other hand, for languages with existential restrictions both, the complexity of deciding the solvability of matching problems and the complexity of actually computing sets of ``interesting" matchers are determined. The results show that existential restrictions make these computational tasks more complex. Whereas for sublanguages of CLASSIC both problems could be solved in polynomial time, this is no longer possible for languages with existential restrictions.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaaderKuesters-KR-2000,
  address = {San Francisco, CA},
  author = {F. {Baader} and R. {K{\"u}sters}},
  booktitle = {Proceedings of the Seventh International Conference on Knowledge Representation and Reasoning (KR2000)},
  editor = {A.G. {Cohn} and F. {Giunchiglia} and B. {Selman}},
  pages = {261--272},
  publisher = {Morgan Kaufmann Publishers},
  title = {Matching in Description Logics with Existential Restrictions},
  year = {2000},
}