Reasoning in Fuzzy Description Logics with General Concept Inclusion Axioms

• Applicant: Professor Dr.-Ing. Franz Baader
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 216489495

• Final Report Year: 2016

Final Report Abstract

The goal of this project was to investigate the border between decidability and undecidability in fuzzy description logics, with a special focus on logics supporting general concept inclusion axioms. Such logics had recently come under investigation due to the failure of tableau algorithms that depend on the finite model property. The idea was to extend previous (un)decidability results and develop new general methods that allow to show results for large classes of fuzzy description logics in a uniform way. For fuzzy description logics with a decidable consistency problem, we were also interested in finding out whether the complexity of reasoning increases in comparison to the underlying classical description logics. In the course of this project, these goals were fulfilled to a high degree. The decidability and precise complexity of consistency checking in most fuzzy description logics is now known. In particular, we were able to generalize previous undecidability results to large classes of fuzzy description logics that extend EL with any kind of negation constructor. For most of the logics not covered by these results, we showed complementary decidability and tight complexity results. For some logics, fuzzy reasoning becomes trivial in the sense that it is equivalent to reasoning in the underlying classical description logics. In contrast, the family of Gödel description logics is still reasonably expressive, and decidability was shown despite the lack of the finite model property. Even for very expressive combinations of constructors, the complexity of reasoning is not increased by considering fuzzy semantics based on the Gödel t-norm. We were also able to show tight complexity bounds for reasoning in finitely valued fuzzy description logics. Finally, we provided some results for less expressive logics, exhibiting a first example of a description logic that has polynomial-time reasoning complexity in the classical case, but becomes exponential when extended with at least one more truth degree. Our results provide an important map of the complexity landscape of fuzzy description logics, which can aid researchers and modeling experts alike in choosing a fuzzy description logic suitable for their needs.

Publications

• “Undecidability of Fuzzy Description Logics”. In: Proc. of the 13th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR’12). Edited by Gerhard Brewka, Thomas Eiter, and Sheila A. McIlraith. AAAI Press, 2012, pages 232–242
  Stefan Borgwardt and Rafael Peñaloza
  
• “Consistency Reasoning in Lattice-Based Fuzzy Description Logics”. In: International Journal of Approximate Reasoning 55.9 (2014), pages 1917–1938
  Stefan Borgwardt and Rafael Peñaloza
  
• “Decidable Gödel Description Logics without the Finitely-Valued Model Property”. In: Proc. of the 14th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR’14). Edited by Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter. AAAI Press, 2014, pages 228–237
  Stefan Borgwardt, Felix Distel, and Rafael Peñaloza
  
• “On the Decidability Status of Fuzzy ALC with General Concept Inclusions”. In: Journal of Philosophical Logic 44.2 (2015), pages 117–146
  Franz Baader, Stefan Borgwardt, and Rafael Peñaloza
  
• “Reasoning in Expressive Description Logics under Infinitely Valued Gödel Semantics”. In: Proc. of the 10th Int. Symp. on Frontiers of Combining Systems (FroCoS’15). Edited by Carsten Lutz and Silvio Ranise. Volume 9322. Lecture Notes in Artificial Intelligence. Springer-Verlag, 2015, pages 49–65
  Stefan Borgwardt and Rafael Peñaloza
  
• “The Complexity of Subsumption in Fuzzy EL”. In: Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI’15). Edited by Qiang Yang and Michael Wooldridge. AAAI Press, 2015, pages 2812–2818
  Stefan Borgwardt, Marco Cerami, and Rafael Peñaloza
  
• “The Limits of Decidability in Fuzzy Description Logics with General Concept Inclusions”. In: Artificial Intelligence 218 (2015), pages 23–55
  Stefan Borgwardt, Felix Distel, and Rafael Peñaloza
  
• “Answering Fuzzy Conjunctive Queries over Finitely Valued Fuzzy Ontologies”. In: Journal on Data Semantics 5.2 (2016), pages 55–75
  Stefan Borgwardt, Theofilos Mailis, Rafael Peñaloza, and Anni-Yasmin Turhan
  
• “Reasoning in Fuzzy Description Logics using Automata”. In: Fuzzy Sets and Systems 298 (2016), pages 22–43
  Stefan Borgwardt and Rafael Pe˜ñaloza