Tractable Probabilistic Description Logic

Algorithms and implementation

author

Andrew Ijano Lopes

supervisor

Marcelo Finger

Description logics are a family of formal knowledge representation languages.

One of them, the EL++, is an expressive logic whose decision procedure is tractable. it shines when you want to work with a large amount of data, helping the healthcare worldwide.

However, simply adding probabilistic constraints leaves its decision complexity untractable.

In this project, we study a reasonably expressive fragment of it, called graphic EL++, and its probabilistic extension, PGEL++.

This fragment alows us to express the axioms as a graph, which inherits tractable decision procedure.

Then, this project aims to develop and implement algorithms for a tractable decision of PGEL++.

We're going to build graph-based machinery to obtain a tractable maxSAT problem for GEL++ and a column generation procedure for deciding PGEL++, which uses the maxSAT solver as an auxiliary procedure.

Check the github repository for the implementation.