Tight Complexity Bounds for Reasoning in the Description Logic {$\mathcal{BEL}$}

Ismail Ilkan CeylanIsmail Ilkan Ceylan, Rafael PeñalozaRafael Peñaloza

$Tight Complexity Bounds for Reasoning in the Description Logic {$\mathcal{BEL}$}$

Download

Ismail Ilkan Ceylan, Rafael Peñaloza
Tight Complexity Bounds for Reasoning in the Description Logic {$\mathcal{BEL}$}
In Eduardo {Fermé} and João {Leite}, eds., Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA 2014), volume 8761 of Lecture Notes in Computer Science, 77--91, 2014. Springer

Details
Bibtex

KurzfassungAbstract
Recently, Bayesian extensions of Description Logics, and in particular the logic BEL,
were introduced as a means of representing certain knowledge that depends on an uncertain context. In this paper we introduce a novel structure, called proof structure, that encodes the contextual information required to deduce subsumption relations from a BEL knowledge base. Using this structure, we show that probabilistic reasoning in BEL can be reduced in polynomial time
to standard Bayesian network inferences, thus obtaining tight complexity bounds for reasoning in BEL.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ CePe-JELIA14,
  author = {Ismail Ilkan {Ceylan} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA 2014)},
  editor = {Eduardo {Ferm{\'e}} and Jo{\~a}o {Leite}},
  pages = {77--91},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Tight Complexity Bounds for Reasoning in the Description Logic {$\mathcal{BEL}$}},
  volume = {8761},
  year = {2014},
}