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.