Algorithms and implementation
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.