Applications and Extensions of PTIME Description Logics With Functional Constraints

The authors review and extend earlier work on the logic CFD, a description logic that allows terminological cycles with universal restrictions over functional roles. In particular, they consider the problem of reasoning about concept subsumption and the problem of computing certain answers for a family of attribute-connected conjunctive queries, showing that both problems are in PTIME. They then consider the effect on the complexity of these problems after adding a concept constructor that expresses concept union, or after adding a concept constructor for the bottom class. Finally, they show that adding both constructors makes both problems EXPTIME-complete.