How Many Toes Do I Have? Parthood and Number Restrictions in Description Logics

Lutz Schröder, Dirk Pattinson

The modelling of parthood relations in description logics via transitive roles often leads to undecidability when combined with number restrictions and role hierarchies. Here, we introduce the description logic PHQ that explicitly supports reasoning about parthood in the presence of qualified number restrictions. Our main results are completeness and decidability in NEXPTIME. Conceptually, we argue that PHQ provides a better semantic fit for many applications: more often than not, parthoods occurring e.g. in biomedical ontologies are expected to be tree-like. In such cases, PHQ supports stronger inferences than standard description logics. Technically this is achieved by explicitly excluding the merging of descendants, which, at the same time, eliminates the prime source of undecidability. We work in the general setting of coalgebraic modal logic, a generic semantic framework for not-necessarily-normal modal logics. This added generality allows the re-use of many of our results for other logics of sometimes quite different flavour.


Subjects: 11. Knowledge Representation; 11.1 Description Logics

Submitted: Jun 16, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.