We make the measurability of our R&D results one of our primary tasks. We want to show to the world that semantic technologies are becoming reality. Find out more about our results and our spin-off companies.

On Fixpoint-based Decision Procedures for Fuzzy Description Logics I

Uwe Keller and Stijn Heymans
Publishing Date:
STI Innsbruck

We present FixIt(fuzzy-ALC), a novel procedure for deciding knowledge base (KB) satisfiability in the Fuzzy Description Logic (FDL) fuzzy-ALC. FixIt(fuzzy-ALC) does not search for tree-structured models as in tableau-based proof procedures, but embodies a fixpoint-computation of canonical models that are not necessarily tree-structured, based on a type-elimination process. Soundness, completeness and termination are proven and the runtime and space complexity are discussed. We give a precise characterization of the worst-case complexity of deciding KB satisfiability in fuzzy-ALC in the general case and show that our method yields a worst-case optimal decision procedure (under reasonable assumptions). To the best of our knowledge it is the first {\em fixpoint-based} decision procedure for FDLs, hence introducing a new class of inference procedures into FDL reasoning.

Author(s) from STI: