Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
KI - Künstliche Intelligenz
Published in: KI - Künstliche Intelligenz 1/2017

26-10-2016 | Research Project

Decidability and Complexity of Fuzzy Description Logics

Authors: Franz Baader, Stefan Borgwardt, Rafael Peñaloza

Published in: KI - Künstliche Intelligenz | Issue 1/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article BDI Logics for BDI Architectures: Old Problems, New Perspectives
next article DFG Research Unit (Forschergruppe) FOR 1513 Hybrid Reasoning for Intelligent Systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

KI - Künstliche Intelligenz

The Scientific journal "KI – Künstliche Intelligenz" is the official journal of the division for artificial intelligence within the "Gesellschaft für Informatik e.V." (GI) – the German Informatics Society - with constributions from troughout the field of artificial intelligence.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Show more products
Literature
1.
Baader F (1996) Using automata theory for characterizing the semantics of terminological cycles. Ann Math Artif Intell 18(2):175–219MathSciNetCrossRefMATH
2.
Baader F, Borgwardt S, Peñaloza R (2015) On the decidability status of fuzzy ALC with general concept inclusions. J Philos Logic 44(2):117–146MathSciNetCrossRefMATH
3.
Baader F, Brandt S, Lutz C (2005) Pushing the EL envelope. In L. P. Kaelbling and A. Saffiotti, editors, Int. Joint Conf. on Artif. Intell. (IJCAI), pp 364–369. Professional Book Center
4.
Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF (2007) The description logic handbook: theory, implementation, and applications. Cambridge University Press, 2nd edn
5.
6.
Baader F, Peñaloza R (2011) Are fuzzy description logics with general concept inclusion axioms decidable? In IEEE Int. Conf. on Fuzzy Systems (FUZZ-IEEE), pp 1735–1742. IEEE Press
7.
Baader F, Peñaloza R (2011) On the undecidability of fuzzy description logics with GCIs and product t-norm. In: Tinelli C., and Sofronie-Stokkermans V (eds), Frontiers of Comb. Syst. (FroCoS), volume 6989 of LNCS, pp 55–70. Springer
8.
Bienvenu M, Ortiz M (2015) Ontology-mediated query answering with data-tractable description logics. In: Faber W, Paschke A (eds) Reasoning web, volume 9203 of LNCS, pp 218–307. Springer
9.
Bobillo F, Bou F, Straccia U (2011) On the failure of the finite model property in some fuzzy description logics. Fuzzy Set Syst 172(1):1–12MathSciNetCrossRefMATH
10.
Bobillo F, Delgado M, Gómez-Romero J (2009) Crisp representations and reasoning for fuzzy ontologies. Int J Uncertain Fuzz. 17(4):501–530MathSciNetCrossRefMATH
11.
Bobillo F, Delgado M, Gómez-Romero J (2013) Reasoning in fuzzy OWL 2 with DeLorean. In: Bobillo F, da Costa PCG, d’Amato C, Fanizzi N, Laskey K, Laskey K, Lukasiewicz, Nickles M, Pool M (eds) Uncertainty reasoning for the semantic Web II, volume 7123 of LNCS, pp 119–138. Springer
12.
13.
Bobillo F, Straccia U (2013) Finite fuzzy description logics and crisp representations. In: Bobillo F, da Costa PCG, d’Amato C, Fanizzi N, Laskey K, Laskey K, Lukasiewicz T, Nickles M, Pool M (eds) Uncertainty Reasoning for the Semantic Web II, volume 7123 of LNCS, pp 99–118. Springer
14.
Bobillo F, Straccia U (2016) The fuzzy ontology reasoner fuzzyDL. Knowl-Based Syst 95:12–34CrossRef
15.
Borgwardt S (2014) Fuzzy description logics with general concept inclusions. PhD thesis, Technische Universität Dresden
16.
Borgwardt S, Cerami M, Peñaloza R (2015) The complexity of subsumption in fuzzy EL. In: Yang Q, Wooldridge M (eds) Int. Joint Conf. on Artif. Intell. (IJCAI), pp 2812–2818. AAAI Press
17.
Borgwardt S, Distel F, Peñaloza R (2012) How fuzzy is my fuzzy description logic? In: Gramlich B, Miller D, Sattler U (eds) Int. Joint Conf. on Automated Reasoning (IJCAR), volume 7364 of LNAI, pp 82–96. Springer
18.
Borgwardt S, Distel F, Peñaloza R (2014) Decidable Gödel description logics without the finitely-valued model property. In: Baral C, De Giacomo G, Eiter T (eds) Princ. of Knowl. Repr. and Reas. (KR), pp 228–237. AAAI Press
19.
Borgwardt S, Distel F, Peñaloza R (2015) The limits of decidability in fuzzy description logics with general concept inclusions. Artif Intell 218:23–55MathSciNetCrossRefMATH
20.
Borgwardt S, Leyva Galano JA, Peñaloza R (2014) The fuzzy description logic G-\({FL_0}\)
21.
Borgwardt S, Mailis T, Peñaloza R, Turhan A-Y (2016) Answering fuzzy conjunctive queries over finitely valued fuzzy ontologies. J Data Sem 5(2):55–75CrossRef
22.
Borgwardt S, Peñaloza R. Algorithms for reasoning in very expressive description logics under infinitely valued Gödel semantics. Int J Appr Reas Submitted
23.
Borgwardt S, Penaloza R (2011) Description logics over lattices with multi-valued ontologies. In: Walsh T (ed) Int Joint Conf. on Artif. Intell. (IJCAI)
24.
Borgwardt S, Peñaloza R (2012) A tableau algorithm for fuzzy description logics over residuated De Morgan lattices. In: Krötzsch M, Straccia U (eds) Web Reas. and Rule Syst. (RR), volume 7497 of LNCS, pp 9–24. Springer
25.
Borgwardt S, Peñaloza R (2012) Undecidability of fuzzy description logics. In: Brewka G, Eiter T, McIlraith SA (eds) Princ. of Knowl. Repr. and Reas. (KR), pp 232–242. AAAI Press
26.
Borgwardt S, Peñaloza R (2013) The complexity of lattice-based fuzzy description logics. J Data Sem 2(1):1–19CrossRef
27.
Borgwardt S, Peñaloza R (2013) Positive subsumption in fuzzy EL with general t-norms. In: Rossi F (ed) Int. Joint Conf. on Artif. Intell. (IJCAI), pp 789–795. AAAI Press
28.
29.
Borgwardt S, Peñaloza R (2014) Finite lattices do not make reasoning in ALCOI harder. In: Bobillo F, Carvalho RN, da Costa PCG, d’Amato C, Fanizzi N, Laskey KB, Laskey KJ, T. Lukasiewicz, M. Nickles, and M. Pool, editors, Uncertainty Reasoning for the Semantic Web III, volume 8816 of LNAI, pp 122–141. Springer
30.
Borgwardt S, Peñaloza R (2015) Reasoning in expressive description logics under infinitely valued Gödel semantics. In: Lutz C, Ranise S (eds) Frontiers of Comb. Syst. (FroCoS), volume 9322 of LNAI, pp 49–65. Springer
31.
32.
Calvanese D, Eiter T, Ortiz M (2009) Regular path queries in expressive description logics with nominals. In C. Boutilier, editor, Int. Joint Conf. on Artif. Intell. (IJCAI), pp 714–720. AAAI Press
33.
Cerami M, Straccia U (2011) On the undecidability of fuzzy description logics with GCIs with Łukasiewicz t-norm. CoRR, abs/1107.4212v3, 2011
34.
Cerami M, Straccia U (2013) On the (un)decidability of fuzzy description logics under Łukasiewicz t-norm. Inf Sci 227:1–21CrossRefMATH
35.
Dasiopoulou S, Kompatsiaris I, Strintzis MG (2009) Applying fuzzy DLs in the extraction of image semantics. J. Data Sem., XIV:105–132
36.
T. Di Noia, M. Mongiello, and U. Straccia. Fuzzy description logics for component selection in software design. In: Bianculli D, Calinescu R, Rumpe B (eds) SEFM’15 Workshops, Selected Papers, volume 9509 of LNCS, pp. 228–239. Springer
37.
Díaz-Rodríguez N, Cadahía O, Cuéllar M, Lilius J, Calvo-Flores M (2014) Handling real-world context awareness, uncertainty and vagueness in real-time human activity tracking and recognition with a fuzzy ontology-based hybrid method. Sensors 14(20):18131–18171CrossRef
38.
Hájek P (1998) Metamathematics of Fuzzy Logic, volume 4 of Trends in logic. Kluwer
39.
40.
Hollunder B (1996) Consistency checking reduced to satisfiability of concepts in terminological systems. Ann Math Artif Intell 18(2–4):133–157MathSciNetCrossRefMATH
41.
Horrocks I, Kutz O, Sattler U (2006) The even more irresistible SROIQ. In: Doherty P, Mylopoulos J, Welty C (eds) Princ. of Knowl. Repr. and Reas. (KR), pp 57–67. AAAI Press
42.
Horrocks I, Sattler U (2004) Decidability of SHIQ with complex role inclusion axioms. Artif Intell 160(1–2):79–104CrossRefMATH
43.
Mailis T, Peñaloza R, Turhan AY (2014) Conjunctive query answering in finitely-valued fuzzy description logics. In: Kontchakov R, Mugnier ML (eds) Web Reas. and Rule Syst. (RR), volume 8741 of LNCS, pp 124–139. Springer
44.
Mailis T, Stoilos G, Simou N, Stamou GB, Kollias S (2012) Tractable reasoning with vague knowledge using fuzzy \({EL^{++}}\). J Intell Inf Syst 39(2):399–440CrossRef
45.
Mailis T, Turhan AY (2014) Employing \({DL-Lite}_R\)-reasoners for fuzzy query answering. In: Supnithi T, Yamaguchi T, Pan JZ, Wuwongse V, Buranarach M (eds) Joint Int. Semantic Technology Conf. (JIST), volume 8943 of LNCS, pp 63–78. Springer
46.
Merz D, Peñaloza R, Turhan AY (2014) Reasoning in ALC with fuzzy concrete domains. In: Lutz C, Thielscher M (eds) German Conf. on Artificial Intelligence (KI), volume 8736 of LNAI, pp 171–182. Springer
47.
Ortiz M, Šimkus M (2012) Reasoning and query answering in description logics. In: Eiter T, Krennwallner T (eds) Reasoning Web, volume 7487 of LNCS, pp 1–53. Springer
48.
Pan JZ, Stamou GB, Stoilos G, Thomas E (2007) Expressive querying over fuzzy DL-Lite ontologies. In: Calvanese D, Franconi E, Haarslev V, Lembo D, Motik B, Turhan AY, Tessaris S (eds) Workshop on description logics (DL), volume 250 of CEUR-WS, pp 427–434
49.
Schild K (1991) A correspondence theory for terminological logics: preliminary report. In: Mylopoulos J, Reiter R (eds) Int. Joint Conf. on Artif. Intell. (IJCAI), pp 466–471. Morgan Kaufmann
50.
Stoilos G, Simou N, Stamou G, Kollias S (2006) Uncertainty and the semantic web. IEEE Intell Syst 21(5):84–87CrossRef
51.
Stoilos G, Stamou GB (2014) Reasoning with fuzzy extensions of OWL and OWL 2. Knowl Inf Syst 40(1):205–242CrossRef
52.
Straccia U (1998) A fuzzy description logic. In: Nat. Conf. on Artificial Intelligence (AAAI), pp 594–599
53.
54.
Straccia U (2004) Uncertainty in description logics: a lattice-based approach. In: Inf. Process. and Manag. of Uncertainty in Knowl.-Based Syst. (IPMU), pp 251–258
55.
Straccia U (2005) Description logics with fuzzy concrete domains. In: Bacchus F, Jaakola T (eds) Uncertainty in artificial intelligence (UAI), pp 559–567. AUAI Press
56.
Straccia U (2006) Answering vague queries in fuzzy DL-Lite. In: Inf. Process. and Manag. of Uncertainty in Knowl.-Based Syst. (IPMU), pp 2238–2245. Éditions EDK
57.
Straccia U (2014) On the top-k retrieval problem for ontology-based access to databases. In: Pivert O, Awomir Zadrozny S (eds) Flexible approaches in data, information and knowledge management, volume 497 of Studies in Computational Intelligence, pp 95–114. Springer
58.
Straccia U, Mucci M (2015) pFOIL-DL: learning (fuzzy) EL concept descriptions from crisp OWL data using a probabilistic ensemble estimation. In: Wainwright RL, Corchado JM, Bechini A, Hong J (eds) Symp. on Applied Computing (SAC), pp 345–352. ACM
59.
Tobies S (2000) The complexity of reasoning with cardinality restrictions and nominals in expressive description logics. J Artif Intell Res 12:199–217MathSciNetMATH
60.
Tresp CB, Molitor R (1998) A description logic for vague knowledge. In: Prade H (ed) Eur. Conf. Artificial Intelligence (ECAI), pp 361–365. John Wiley & Sons
61.
Tsatsou D, Dasiopoulou S, Kompatsiaris I, Mezaris V (2014) LiFR: a lightweight fuzzy DL reasoner. In: Presutti V, Blomqvist E, Troncy R, Sack H, Papadakis I, Tordal A (eds) ESWC Satellite Events, volume 8798 of LNCS, pp 263–267. Springer
62.
Metadata
Title
Decidability and Complexity of Fuzzy Description Logics
Authors
Franz Baader
Stefan Borgwardt
Rafael Peñaloza
Publication date
26-10-2016
Publisher
Springer Berlin Heidelberg
Published in
KI - Künstliche Intelligenz / Issue 1/2017
Print ISSN: 0933-1875
Electronic ISSN: 1610-1987
DOI
https://doi.org/10.1007/s13218-016-0459-3

Other articles of this Issue 1/2017

KI - Künstliche Intelligenz 1/2017 Go to the issue

Interview

Quo vadis, AI?

Doctoral and Postdoctoral Dissertations

Quantitative Methods for Similarity in Description Logics

Editorial

Editorial

Survey

Many Facets of Reasoning Under Uncertainty, Inconsistency, Vagueness, and Preferences: A Brief Survey

Community

News

Technical Contribution

On the Compliance of Rationality Postulates for Inconsistency Measures: A More or Less Complete Picture

Premium Partner

    Image Credits