Towards dichotomy results for sub-Boolean description logics
A.Kurucz, F.Wolter, M.Zakharyaschev
 
EL is a tractable description logic serving as the logical underpinning of large-scale ontologies. 
We launch a systematic investigation of the boundary between tractable and intractable reasoning in EL 
under relational constraints. E.g., we show that there are (modulo equivalence) exactly 3 universal
constraints on a transitive and reflexive relation under which reasoning is tractable: 
being a singleton set, an equivalence relation, or the empty constraint. 
We prove a number of results of this type and discuss a spectrum of open problems including 
generalisations to the algebraic semantics for EL (semi-lattices with monotone operators).