A Closer Look at the Probabilistic Description Logic Prob-EL (bibtex)

by Victor Gutierrez-Basulto, Jean Christoph Jung, Carsten Lutz and Lutz Schröder

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 2ExpTime and there were reasons to believe in completeness for this class.

Reference:

Victor Gutierrez-Basulto, Jean Christoph Jung, Carsten Lutz and Lutz Schröder: A Closer Look at the Probabilistic Description Logic Prob-EL, In Wolfram Burgard, Dan Roth, eds.: Proc. 25th Conference on Artificial Intelligence (AAAI-11), pp. 197–202, AAAI Press, 2011.

Bibtex Entry:

@InProceedings{GutierrezBasultoEA11,
  author = {Victor Gutierrez-Basulto and Jean Christoph Jung and Carsten Lutz and Lutz Schr{\"o}der},
  title = {A Closer Look at the Probabilistic Description Logic Prob-EL},
  year = {2011},
  editor = {Wolfram Burgard and Dan Roth},
  booktitle = {Proc. 25th Conference on Artificial Intelligence (AAAI-11)},
  publisher = {AAAI Press},
  pages = {197-202},
  keywords = {Probabilistic description logic EL complexity convexity},
  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 2ExpTime and there were
reasons to believe in completeness for this class.
},
}