On P/NP Dichotomies for EL subsumption under relational constraints
Agi Kurucz, Frank Wolter, Michael Zakharyaschev · BIROn (Birkbeck, University of London) · 2011
Abstract. We consider the problem of characterising relational constraints under which TBox reasoning in EL is tractable. We obtain P vs. coNP-hardness dichotomies for tabular constraints and constraints imposed on a single reflexive role. 1