Probabilistic Description Logics for Subjective Uncertainty (bibtex)

by Carsten Lutz and Lutz Schröder

Abstract:

We propose a new family of probabilistic description logics (DLs) that, in contrast to most existing approaches, are derived in a principled way from Halpern’s probabilistic &64257;rst-order logic. The resulting probabilistic DLs have a two-dimensional semantics similar to certain popular combinations of DLs with temporal logic and are well-suited for capturing subjective probabilities. Our main contribution is a detailed study of the complexity of reasoning in the new family of probabilistic DLs, showing that it ranges from PTIME for weak variants based on the lightweight DL EL to undecidable for some expressive variants based on the DL ALC.

Reference:

Carsten Lutz and Lutz Schröder: Probabilistic Description Logics for Subjective Uncertainty, In Fangzhen Lin, Ulrike Sattler, Miroslaw Truszczynski, eds.: Principles of Knowledge Representation and Reasoning (KR 2010), pp. 393–403, AAAI Press; Menlo Park, CA, 2010. [preprint]

Bibtex Entry:

@InProceedings{LutzSchroeder10,
  author = {Carsten Lutz and Lutz Schr{\"o}der},
  title = {Probabilistic Description Logics for Subjective Uncertainty},
  year = {2010},
  editor = {Fangzhen Lin and Ulrike Sattler and Miroslaw Truszczynski},
  booktitle = {Principles of Knowledge Representation and Reasoning (KR 2010)},
  publisher = {AAAI Press; Menlo Park, CA},
  pages = {393-403},
  keywords = {probabilistic description logic EL ALC},
  comment = { <a href = "http://www8.informatik.uni-erlangen.de/~schroeder/papers/probDL.pdf"> [preprint] </a>},
  abstract = {We propose a new family of probabilistic description logics
(DLs) that, in contrast to most existing approaches, are derived in a principled way from Halpern’s probabilistic &#64257;rst-order logic. The resulting probabilistic DLs have a two-dimensional semantics similar to certain popular combinations of DLs with temporal logic and are well-suited for capturing subjective probabilities. Our main contribution is a detailed study of the complexity of reasoning in the new family
of probabilistic DLs, showing that it ranges from PTIME for
weak variants based on the lightweight DL EL to undecidable
for some expressive variants based on the DL ALC.},
}