JavaScript is required to use this site. Please enable JavaScript in your browser settings.

Supervisor

Complexity of Matching in the Description Logic EL without the Top Concept

Status: finished / Type of Theses: Master theses / Location: Dresden

Matching and unification have been proposed as reasoning problems in description logics that can, for example, be used to detect redundancies or filter out unimportant aspects of large concept descriptions in ontologies, such as SNOMED CT. In the particular case of matching in EL, the complexity of the problem was shown to be NP-complete. However, the problem has not been investigated for the DL ELnoTop, which is the fragment of EL that does not allow the use of the Top concept. In this thesis, we explore the computational complexity of matching in ELnoTop. We consider different variants of the matching problem in ELnoTop, both in the case of an empty TBox and in the presence of general TBoxes. We prove that in general the complexity of matching increases if the Top concept is not allowed.

funded by:
Gefördert vom Bundesministerium für Bildung und Forschung.
Gefördert vom Freistaat Sachsen.