Practical Reasoning with Nominals in the EL Family of Description Logics


Yevgeny Kazakov, Markus Krötzsch, František Simančík

Practical Reasoning with Nominals in the EL Family of Description Logics

Abstract. The EL family of description logics (DLs) has been designed to provide a restricted syntax for commonly used DL constructors with the goal to guarantee polynomial complexity of reasoning. Yet, polynomial complexity does not always mean that the underlying reasoning procedure is efficient in practice. In this paper we consider a simple DL ELO from the EL family that admits nominals, and argue that existing polynomial reasoning procedures for ELO can be impractical for many realistic ontologies. To solve the problem, we describe an optimization strategy in which the inference rules required for reasoning with nominals are avoided as much as possible. The optimized procedure is evaluated within the reasoner ELK and demonstrated to perform well in practice.

Published at KR2012 (Conference paper)

Download PDF (last update: 13 Jul 2012)

Citation details


The main reference for ELK is The Incredible ELK. Please use this in citations for the general system. The above paper is specifically about reasoning with nominals in EL, and includes some material that is not found elsewhere.

The above link points to the extended technical report that includes all proofs. The AAAI website has the conference version of this paper.

More information about the software used in this paper and pointers to further publications can be found on the page about ELK Reasoner.


Description logics, ELK Reasoner