Description Logics with Abstraction and Refinement: From ALC to EL

We study extensions of description logics from the widely used EL family with operators that make it possible to speak about different levels of abstraction. We analyze the computational complexity of reasoning and show that often, this complexity is significantly lower than in the corresponding extension of the more expressive description logic ALC. By slightly varying the semantics, we also obtain a case that admits reasoning in polynomial time.