Decidability and Complexity of Fuzzy Description Logics

Abstract

Fuzzy description logics (FDLs) have been introduced to represent concepts for which membership cannot be determined in a precise way, i.e., where instead of providing a strict border between being a member and not being a member, it is more appropriate to model a gradual change from membership to non-membership. First approaches for reasoning in FDLs where based either on a reduction to reasoning in classical description logics (DLs) or on adaptations of reasoning approaches for DLs to the fuzzy case. However, it turned out that these approaches in general do not work if expressive terminological axioms, called general concept inclusions (GCIs), are available in the FDL. The goal of this project was a comprehensive study of the border between decidability and undecidability for FDLs with GCIs, as well as determining the exact complexity of the decidable logics. As a result, we have provided an almost complete classification of the decidability and complexity of FDLs with GCIs.