Matching in Description Logics with Existential Restrictions

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

Datei:BaaderKuesters-DL-1999.ps.gz

Download

Franz Baader, R. Küsters
Matching in Description Logics with Existential Restrictions
In P. Lambrix and A. Borgida and M. Lenzerini and R. Möller and P. Patel-Schneider, eds., Proceedings of the International Workshop on Description Logics 1999 (DL'99), CEUR-WS, 1999. Linköping University

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: Proceedings online available from http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-22/
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaaderKuesters-DL-1999,
  address = {Sweden},
  author = {F. {Baader} and R. {K{\"u}sters}},
  booktitle = {Proceedings of the International Workshop on Description Logics 1999 (DL'99)},
  editor = {P. {Lambrix} and A. {Borgida} and M. {Lenzerini} and R. {M{\"o}ller} and P. {Patel-Schneider}},
  note = {Proceedings online available from {http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-22/}},
  number = {22},
  publisher = {Link{\"o}ping University},
  series = {CEUR-WS},
  title = {Matching in Description Logics with Existential Restrictions},
  year = {1999},
}