Proceedings

Positive Subsumption in Fuzzy EL with General t-Norms

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 789-794.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

The Description Logic EL is used to formulate several large biomedical ontologies. Fuzzy extensions of EL can express the vagueness inherent in many biomedical concepts. We study the reasoning problem of deciding positive subsumption in fuzzy EL with semantics based on general t-norms. We show that the complexity of this problem depends on the specific t-norm chosen. More precisely, if the t-norm has zero divisors, then the problem is co-NP-hard; otherwise, it can be decided in polynomial time. We also show that the best subsumption degree cannot be computed in polynomial time if the t-norm contains the Łukasiewicz t-norm.

  1. [Baader et al., 2005] Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the EL envelope. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, Proc. IJ- CAI'05, pages 364-369. Professional Book Center, 2005.
  2. [Baader et al., 2007] Franz Baader, Diego Calvanese, Deb- orah L. McGuinness, Daniele Nardi, and Peter F. Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2nd edition, 2007.
  3. [Baader, 2003] Franz Baader. Terminological cycles in a de- scription logic with existential restrictions. In Georg Got- tlob and Toby Walsh, editors, Proc. IJCAI'03, pages 325- 330. IJCAI
  4. Morgan Kaufmann, 2003.
  5. [Bobillo and Straccia, 2013] Fernando Bobillo and Umberto Straccia. Finite fuzzy description logics and crisp repre- sentations. In Fernando Bobillo, Paulo C. G. da Costa, Claudia d'Amato, Nicola Fanizzi, Kathryn Laskey, Ken Laskey, Thomas Lukasiewicz, Matthias Nickles, and Michael Pool, editors, Uncertainty Reasoning for the Se- mantic Web II, volume 7123 of LNCS, pages 102-121. Springer, 2013.
  6. [Borgwardt and Peñaloza, 2012a] Stefan Borgwardt and Rafael Peñaloza. Non Gödel negation makes unwitnessed consistency undecidable. In Yevgeny Kazakov, Domenico Lembo, and Frank Wolter, editors, Proc. DL'12, volume 846 of CEUR-WS, pages 411-421, 2012.
  7. [Borgwardt and Peñaloza, 2012b] Stefan Borgwardt and Rafael Peñaloza. Undecidability of fuzzy description logics. In Gerhard Brewka, Thomas Eiter, and Sheila A. McIlraith, editors, Proc. KR'12, pages 232-242. AAAI Press, 2012.
  8. [Borgwardt and Peñaloza, 2013] Stefan Borgwardt and Rafael Peñaloza. The complexity of lattice-based fuzzy description logics. J. Data Semant., 2(1):1-19, 2013.
  9. [Borgwardt et al., 2012a] Stefan Borgwardt, Felix Distel, and Rafael Peñaloza. Gödel negation makes unwit- nessed consistency crisp. In Yevgeny Kazakov, Domenico Lembo, and Frank Wolter, editors, Proc. DL'12, volume 846 of CEUR-WS, pages 103-113, 2012.
  10. [Borgwardt et al., 2012b] Stefan Borgwardt, Felix Distel, and Rafael Peñaloza. How fuzzy is my fuzzy description logic? In Bernhard Gramlich, Dale Miller, and Uli Sat- tler, editors, Proc. IJCAR'12, volume 7364 of LNAI, pages 82-96. Springer, 2012.
  11. [Brandt, 2004] Sebastian Brandt. Polynomial time reasoning in a description logic with existential restrictions, GCI ax- ioms, and -what else? In Ramon López de Mántaras and Lorenza Saitta, editors, Proc. ECAI'04, pages 298-302. IOS Press, 2004.
  12. [Cerami and Straccia, 2013] Marco Cerami and Umberto Straccia. On the (un)decidability of fuzzy description logics under Łukasiewicz t-norm. Information Sciences, 227:1-21, 2013.
  13. [Cignoli and Torrens, 2003] Roberto Cignoli and Antoni Torrens. Hájek basic fuzzy logic and Łukasiewicz infinite- valued logic. Archive for Mathematical Logic, 42(4):361- 370, 2003.
  14. [Hájek, 2001] Petr Hájek. Metamathematics of Fuzzy Logic (Trends in Logic). Springer, 2001.
  15. [Hájek, 2005] Petr Hájek. Making fuzzy description logic more general. Fuzzy Set. Syst., 154(1):1-15, 2005.
  16. [Hájek, 2006] Petr Hájek. Computational complexity of t- norm based propositional fuzzy logics with rational truth constants. Fuzzy Set. Syst., 157(5):677-682, 2006.
  17. [Karp, 1972] Richard Karp. Reducibility among combina- torial problems. In Raymond E. Miller and James W. Thatcher, editors, Proc. of a Symp. on the Complexity of Computer Computations, pages 85-103. Plenum Press, 1972.
  18. [Klement et al., 2000] Erich Peter Klement, Radko Mesiar, and Endre Pap. Triangular Norms. Trends in Logic, Studia Logica Library. Springer, 2000.
  19. [Mailis et al., 2012] Theofilos Mailis, Giorgos Stoilos, Nikolaos Simou, Giorgos Stamou, and Stefanos Kollias. Tractable reasoning with vague knowledge using fuzzy EL ++ . J. Intell. Inf. Syst., 39:399-440, 2012.
  20. [Mostert and Shields, 1957] Paul S. Mostert and Allen L. Shields. On the structure of semigroups on a compact man- ifold with boundary. Ann. Math., 65(1):117-143, 1957.
  21. [Straccia, 2001] Umberto Straccia. Reasoning within fuzzy description logics. J. Artif. Intell. Res., 14:137-166, 2001.
  22. [Tresp and Molitor, 1998] Christopher B. Tresp and Ralf Molitor. A description logic for vague knowledge. In Henri Prade, editor, Proc. ECAI'98, pages 361-365.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards