Matching with respect to general concept inclusions in the Description Logic EL

Franz BaaderFranz Baader, Barbara MorawskaBarbara Morawska

Download

Franz Baader, Barbara Morawska
Matching with respect to general concept inclusions in the Description Logic EL
In Temur Kutsia and Christophe Ringeissen, eds., Proceedings of the 28th International Workshop on Unification (UNIF'14), RISC-Linz Report Series No. 14-06, 22-26, 2014

Details
Bibtex

KurzfassungAbstract
Matching concept descriptions against concept patterns wasintroduced as a new inference task in Description Logics (DLs) almost20 years ago, motivated by applications in the Classic system. For theDL EL, it was shown in 2000 that the matching problem is NP-complete.It then took almost 10 years before this NP-completeness result couldbe extended from matching to unification in EL. The next big challengewas then to further extend these results from matching and unificationwithout a TBox to matching and unification w.r.t. a general TBox, i.e.,a finite set of general concept inclusions. For unification, we could showsome partial results for general TBoxes that satisfy a certain restrictionon cyclic dependencies between concepts, but the general case is stillopen. For matching, we were able to solve the general case: we can showthat matching in EL w.r.t. general TBoxes is NP-complete. We alsodetermine some tractable variants of the matching problem.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaMo-UNIF14,
  address = {Vienna, Austria},
  author = {Franz {Baader} and Barbara {Morawska}},
  booktitle = {Proceedings of the 28th International Workshop on Unification ({UNIF'14})},
  editor = {Temur {Kutsia} and Christophe {Ringeissen}},
  pages = {22--26},
  series = {RISC-Linz Report Series No. 14-06},
  title = {Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$},
  year = {2014},
}