A Closer Look at the Probabilistic Description Logic Prob-EL

Víctor Gutiérrez-Basulto, Jean Christoph Jung, Carsten Lutz, Lutz Schröder

AAAI 2011 pp. 197-202

doi:10.1609/AAAI.V25I1.7856 /aaai/2011/gutierrezbasulto2011aaai-closer/

Abstract

We study probabilistic variants of the description logic EL. For the case where probabilities apply only to concepts, we provide a careful analysis of the borderline between tractability and ExpTime-completeness. One outcome is that any probability value except zero and one leads to intractability in the presence of general TBoxes, while this is not the case for classical TBoxes. For the case where probabilities can also be applied to roles, we show PSpace-completeness. This result is (positively) surprising as the best previously known upper bound was 2-ExpTime and there were reasons to believe in completeness for this class.

PDF AAAI Semantic Scholar

Cite

Text

Gutiérrez-Basulto et al. "A Closer Look at the Probabilistic Description Logic Prob-EL." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7856

Markdown

[Gutiérrez-Basulto et al. "A Closer Look at the Probabilistic Description Logic Prob-EL." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/gutierrezbasulto2011aaai-closer/) doi:10.1609/AAAI.V25I1.7856

BibTeX

@inproceedings{gutierrezbasulto2011aaai-closer,
  title     = {{A Closer Look at the Probabilistic Description Logic Prob-EL}},
  author    = {Gutiérrez-Basulto, Víctor and Jung, Jean Christoph and Lutz, Carsten and Schröder, Lutz},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {197-202},
  doi       = {10.1609/AAAI.V25I1.7856},
  url       = {https://mlanthology.org/aaai/2011/gutierrezbasulto2011aaai-closer/}
}