DevelopinThe Bayesian Description Logic BALC

Description Logics (DLs) that support uncertainty are not as well studied as their crisp alternatives. This limits their application in many real world domains, which often require reasoning about uncertain or contradictory information. In this thesis we present the Bayesian Description Logic BALC, which takes existing work on Bayesian Description Logics and applies it to the classical Description Logic ALC. We define five reasoning problems for BALC; two versions of concept satisfiability (called total and partial respectively), knowledge base consistency, three subsumption problems (positive subsumption, p-subsumption, exact subsumption), instance checking, and the most likely context problem. Consistency, satisfiability, and instance checking have not previously been studied in the context of contextual Bayesian DLs and as such this is new work. We then go on to provide algorithms that solve all of these reasoning problems, with the exception of the most likely context problem. We found that all reasoning problems in BALC are in the same complexity class as their classical variants, provided that the size of the Bayesian Network is included in the size of the knowledge base. That is, all reasoning problems mentioned above (excluding most likely context) are exponential in the size of the knowledge base and the size of the Bayesian Network.

Grantor dc:publisher.institution

Department of Computer Science

Year dc:date.issued

2018

Author dc:creator

• Botha, Leonard

Advisors dc:contributor.advisor

• Meyer, Thomas
• Peñaloza, Rafael

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/11427/29350

OAI identifier oai:identifier

oai:open.uct.ac.za:11427/29350