Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$

Franz BaaderFranz Baader, Barbara MorawskaBarbara Morawska

$Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$$

Download

Franz Baader, Barbara Morawska
Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$
In Carsten {Lutz} and Michael {Thielscher}, eds., Proceedings of the 37th German Conference on Artificial Intelligence (KI'14), volume 8736 of Lecture Notes in Artificial Intelligence, 135--146, 2014. Springer

Details
Bibtex

KurzfassungAbstract
Matching concept descriptions against concept patterns was introduced as a new inference task in Description Logics (DLs) almost 20 years ago, motivated by applications in the Classic system. For the DL EL, it was shown in 2000 that matching without a TBox is NP-complete. In this paper we show that matching in EL w.r.t. general TBoxes (i.e., finite sets of general concept inclusions, GCIs) is in NP by introducing a goal-oriented matching algorithm that uses non-deterministic rules to transform a given matching problem into a solved form by a polynomial number of rule applications. We also investigate some tractable variants of the matching problem w.r.t. general TBoxes.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BaMo-KI2014,
  author = {Franz {Baader} and Barbara {Morawska}},
  booktitle = {Proceedings of the 37th German Conference on Artificial Intelligence (KI'14)},
  editor = {Carsten {Lutz} and Michael {Thielscher}},
  pages = {135--146},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$},
  volume = {8736},
  year = {2014},
}