AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Applications and Extensions of PTIME Description Logics with Functional Constraints
David Toman, Grant Weddell

Last modified: 2009-06-25


We review and extend earlier work on the logic CFD, a description logic that allows terminological cycles with universal restrictions over functional roles. In particular, we 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. We 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, we show that adding both constructors makes both problems EXPTIME-complete.

Full Text: PDF