Automation of the Problem of Unification in Description Logics

UNIFDL

The project belongs to a line of the ongoing research on the unification in the area of Description Logic. Description Logic (DL) is a formalism used for knowledge representation, where the knowledge is captured in complex concepts constructed from a set of primary terms with formal constructors. DL enables an application of automated inferences over a knowledge base such like answering queries in a smart way, computing concept hierarchies, detecting errors. The knowledge bases (sets of definitions of complex concepts), based on the constructors of DL, are called DL-knowledge bases or ontologies.

Our Goal

In this project we want to design an algorithm solving unification in a DL FLE. FLE avails of an expressive power sufficient to formalize all the knowledge contained in the targeted ontologies. The examples of such ontologies are
SNOMED CT, GALEN, FMA which represent medical, anatomical knowledge, and they are the intended area of the application of our research.
The unification problem is given in this context, as an input of a pair of complex concepts. The algorithm solving this problem should construct a set of definitions for hereto undefined primitive concepts occurring in the input such that, with these definitions the concepts in the input become unified, i.e. identical or equivalent. Subsequently, the set of
definitions obtained in this way has to be assessed by an expert, who can decide if they make sense. If the answer is
positive, the ontology can be repaired: the redundancy removed and the new definitions added. Thus, the unification algorithm may be of great help for the ontology engineers who work constantly on the extensions of the knowledge bases.

pexels-jeswin-thomas-3781338

Why Choose Us

Benefit 1

A short description of the benefit.

Benefit 2

A short description of the benefit.

Benefit 3

A short description of the benefit.

Benefit 4

A short description of the benefit.

Project Description

Various DLs differ between themselves in their expressive power. Greater expressive power often comes with a price of more complex algorithms for a given task. Hence, it makes sense to start with a smaller logic in order to obtain a practical solution to a problem. In the area of solving unification in DLs the research has started with the small fragments of restricted expressivity, the DLs FL0 and EL. Algorithms for the unification in both of these logics are known, but unification for FL0 is ExpTime-complete even in the best case. Unification in EL is NP-complete.
The DL FLE combines the constructors of FL0 and EL. From algebraic point of view, the equivalence of concepts defined in FL0 is the equational theory ACUIh, where A stands for associativity, C for commutativity, U for unit, I for idempotence of conjunction and h denotes functions that are homomorphic. The equational theory for EL is also ACUI plus monotonic property for its specific constructors (existential restrictions). Hence, solving the unification problem in FLE, we solve it also for the theory ACUIh with monotonic operators.
Our hypothesis is that the unification in the DL FLE is ExpTime complete, as it is also for FL0 alone. Our aim is to discover an algorithm that is only worst case ExpTime and for many other cases will have an acceptable complexity. We expect that the discovery of the algorithm for the unification in FLE will be a breakthrough for the applications of unification in the ontologies, because of its expressive power.
pexels-cottonbro-studio-5184957

This research is part of the project No. 2022/47/P/ST6/03196 within the POLONEZ BIS
programme co-funded by the National Science Centre and the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant
agreement No. 945339.