Pushing the CFDnc Envelope

ABSTRACT. We consider the consequences on basic reasoning problems of allowing negated primitive concepts on left-hand-sides of inclusion dependencies in the description logic dialect CFDnc. Although earlier work has shown that this makes CQ answering coNP-complete, we show that TBox consistency and concept satisfiability remain in PTIME. We also show that knowledge base consistency and instance retrieval remain in PTIME if a CFDnc knowledge base satisfies a number of additional conditions, and that failing any one of these conditions will alone lead to intractability for these problems.