Top

Journal on Data Semantics

Published in:

01-03-2013 | Original Article

The Complexity of Lattice-Based Fuzzy Description Logics

From to

Authors: Stefan Borgwardt, Rafael Peñaloza

Published in: Journal on Data Semantics | Issue 1/2013

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

search-config

AI-assisted search

Off

Abstract

We study the complexity of reasoning in fuzzy description logics with semantics based on finite residuated lattices. For the logic \(\mathcal SHI \), we show that deciding satisfiability and subsumption of concepts, with or without a TBox, are ExpTime-complete problems. In \(\mathcal{ALCHI }\) and a variant of \(\mathcal{SI }\), these decision problems become PSpace-complete when restricted to acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp description logics between \(\mathcal{ALC }\) and \(\mathcal SHI \).

next article A Social Semantic Web Access Control Model

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

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

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

Available only for authorised users

http://www.ihtsdo.org/snomed-ct/.

http://www.opengalen.org/.

http://www.w3.org/TR/owl2-overview/.

The paper [17] actually considers the modal logic K, but the results can be easily transferred to \(\mathcal{ALC }\).

In \({L\text{-}\mathcal{SI }_\mathsf c }\), roles are restricted to be crisp.

For special lattices, in particular total orders with the so-called Zadeh semantics, this blowup can be avoided [30].

It is easy to find the remaining \(n-m\) witnesses. For each \(y\in \Delta ^\mathcal I \) we have \(r^\mathcal I (x,y)\,{\otimes } \,C^\mathcal I (y)\le (\exists r.C)^\mathcal I (x)\) and thus, any choice of additional elements of the domain would suffice.

Recall that we consider the lattice \(L\) to be fixed, and thus it is not part of the input.

The acyclicity of \(\mathcal T \) ensures that this is well-defined.

This definition is based on the construction for crisp \(\mathcal SHI \) [24].

Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF (eds) (2007) The description logic handbook: theory, implementation, and applications, 2nd edn. Cambridge University Press, CambridgeMATH

Baader F, Hladik J, Peñaloza R (2008) Automata can show PSPACE results for description logics. Inf Comput 206(9–10):1045–1056. doi:10.1016/j.ic.2008.03.006

Baader F, Peñaloza R (2011) Are fuzzy description logics with general concept inclusion axioms decidable? In: Proceedings of the 2011 IEEE international conference on fuzzy systems (FUZZ-IEEE’11), pp 1735–1742. IEEE Computer Society Press, New York. doi:10.1109/FUZZY.2011.6007520

Baader F, Peñaloza R (2011) On the undecidability of fuzzy description logics with GCIs and product \(t\)-norm. In: Tinelli C, Sofronie-Stokkermans V (eds) Proceedings of the 8th international symposium on frontiers of combining systems (FroCoS’11). Lecture notes in computer science, vol 6989. Springer, Berlin, pp 55–70. doi:10.1007/978-3-642-24364-6_5

Belnap ND (1977) A useful four-valued logic. In: Epstein G, Dunn JM (eds) Modern uses of multiple-valued logic. Reidel Publishing Company, Dordrecht, pp 7–37

Bobillo F, Bou F, Straccia U (2011) On the failure of the finite model property in some fuzzy description logics. Fuzzy Sets Syst 172(1):1–12. doi:10.1016/j.fss.2011.02.012 MathSciNetMATHCrossRef

Bobillo F, Delgado M, Gómez-Romero J, Straccia U (2012) Joining gödel and zadeh fuzzy logics in fuzzy description logics. Int J Uncertainty Fuzziness Knowl Based Syst 20(4):475–508MATHCrossRef

Bobillo F, Straccia U (2007) A fuzzy description logic with product \(t\)-norm. In: Proceedings of the 2007 IEEE international conference on fuzzy systems (FUZZ-IEEE’07). IEEE Computer Society Press, New York, pp 1–6: doi:10.1109/FUZZY.2007.4295443

Bobillo F, Straccia U (2009) Fuzzy description logics with general \(t\)-norms and datatypes. Fuzzy Sets Syst 160(23):3382–3402. doi: 10.1016/j.fss.2009.03.006 MathSciNetMATHCrossRef

10.

Bobillo F, Straccia U (2010) Finite fuzzy description logics: a crisp representation for finite fuzzy \(\cal{ALCH}\). In: Bobillo F, Carvalho R, da Costa PCG, D’Amato C, Fanizzi N, Laskey KB, Laskey KJ, Lukasiewicz T, Martin T, Nickles M, Pool M (eds) Proceedings of the 6th international workshop on uncertainty reasoning for the semantic web (URSW’10), CEUR Workshop Proceedings, vol 654, pp 61–72. http://ceur-ws.org/Vol-654/paper6.pdf

11.

Bobillo F, Straccia U (2011) Reasoning with the finitely many-valued Łukasiewicz fuzzy description logic \(\cal{SROIQ}\). Inf Sci 181:758–778. doi: j.ins.2010.10.020 MathSciNetMATHCrossRef

12.

Borgwardt S, Peñaloza R (2011) Description logics over lattices with multi-valued ontologies. In: Walsh T (ed) Proceedings of the 22nd international joint conference on artifical intelligence (IJCAI’11). AAAI Press, Menlo Park, pp 768–773. doi:10.5591/978-1-57735-516-8/IJCAI11-135

13.

Borgwardt S, Peñaloza R (2011) Finite lattices do not make reasoning in \(\cal{ALCI}\) harder. In: Bobillo F, Carvalho R, da Costa PCG, d’Amato C, Fanizzi N, Laskey KB, Laskey KJ, Lukasiewicz T, Martin T, Nickles M, Pool M (eds) Proceedings of the 7th international workshop on uncertainty reasoning for the semantic web (URSW’11), CEUR workshop proceedings, vol 778, pp 51–62. http://ceur-ws.org/Vol-778/paper5.pdf

14.

Borgwardt S, Peñaloza R (2011) Fuzzy ontologies over lattices with \(t\)-norms. In: Rosati R, Rudolph S, Zakharyaschev M (eds) Proceedings of the 2011 international workshop on description logics (DL’11), CEUR Workshop Proceedings, vol 745, pp 70–80. http://ceur-ws.org/Vol-745/paper_1.pdf

15.

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) Proceedings of the 6th international conference on web reasoning and rule systems (RR’12), Lecture notes in computer science, vol 7497. Springer, Berlin, pp 9–24. doi:10.1007/978-3-642-33203-6_3

16.

Borgwardt S, Peñaloza R (2012) Undecidability of fuzzy description logics. In: Brewka G, Eiter T, McIlraith SA (eds) Proceedings of the 13th international conference on principles of knowledge representation and reasoning (KR 2012). AAAI Press, Rome, pp 232–242

17.

Bou F, Cerami M, Esteva F (2011) Finite-valued Łukasiewicz modal logic is PSPACE-complete. In: Walsh T (ed) Proceedings of the 22nd international joint conference on artifical intelligence (IJCAI’11). AAAI Press, Menlo Park, pp 774–779. doi:10.5591/978-1-57735-516-8/IJCAI11-136

18.

Cerami M, Straccia U (2011) On the undecidability of fuzzy description logics with GCIs with Łukasiewicz \(t\)-norm . http://arxiv.org/abs/1107.4212

19.

De Cooman G, Kerre EE (1993) Order norms on bounded partially ordered sets. J Fuzzy Math 2:281–310

20.

Goguen JA (1967) L-fuzzy sets. J Math Anal Appl 18(1):145–174. doi:10.1016/0022-247X(67)90189-8 MathSciNetMATHCrossRef

21.

Grätzer G (2003) General lattice theory, 2nd edn. Birkhäuser, BaselMATH

22.

Hájek P (2001) Metamathematics of fuzzy logic (trends in logic). Springer, Berlin

23.

Hájek P (2005) Making fuzzy description logic more general. Fuzzy Sets Syst 154(1):1–15. doi:10.1016/j.fss.2005.03.005 MATHCrossRef

24.

Horrocks I, Sattler U (1999) A description logic with transitive and inverse roles and role hierarchies. J Logic Comput 9(3):385–410. doi:10.1093/logcom/9.3.385 MathSciNetMATHCrossRef

25.

Horrocks I, Sattler U, Tobies S (2000) Practical reasoning for very expressive description logics. J Int Group Pure Appl Logic 8(3):239–263. doi:10.1093/jigpal/8.3.239

26.

Lukasiewicz T, Straccia U (2008) Managing uncertainty and vagueness in description logics for the semantic web. J Web Seman 6(4):291–308. doi:10.1016/j.websem.2008.04.001

27.

Molitor R, Tresp CB (2000) Extending description logics to vague knowledge in medicine. In: Szczepaniak PS, Lisboa PJG, Kacprzyk J (eds) Fuzzy systems in medicine, studies in fuzziness and soft computing, vol 41. Springer, Berlin, pp 617–635. http://www.springer.com/public+health/book/978-3-7908-1263-3

28.

Schild K (1991) A correspondence theory for terminological logics: preliminary report. In: Mylopoulos J, Reiter R (eds) Proceedings of the 12th international joint conference on artificial intelligence (IJCAI’91). Morgan Kaufmann, San Francisco, pp 466–471. http://ijcai.org/Past%20Proceedings/IJCAI-91-VOL1/PDF/072.pdf

29.

Schmidt-Schauß M, Smolka G (1991) Attributive concept descriptions with complements. Artif Intell 48(1):1–26. doi:10.1016/0004-3702(91)90078-X MATHCrossRef

30.

Straccia U (2006) Description logics over lattices. Int J Uncertainty Fuzziness Knowl Based Syst 14(1):1–16. doi:10.1142/S0218488506003807 MathSciNetMATHCrossRef

31.

Tobies S (2001) Complexity results and practical algorithms for logics in knowledge representation. Ph.D. thesis, RWTH Aachen. http://lat.inf.tu-dresden.de/research/phd/#Tobies-PhD-2001

32.

Vardi MY, Wolper P (1986) Automata-theoretic techniques for modal logics of programs. J Comput Syst Sci 32(2):183–221. doi:10.1016/0022-0000(86)90026-7 MathSciNetMATHCrossRef

33.

Zadeh LA (1965) Fuzzy sets. Inf. Control 8(3):338–353MathSciNetMATHCrossRef

34.

Zherui M, Wangming W (1991) Logical operators on complete lattices. Inf Syst 55(1–3):77–97. doi:10.1016/0020-0255(91)90007-H MATH

Title: The Complexity of Lattice-Based Fuzzy Description Logics
From to
Authors: Stefan Borgwardt
Rafael Peñaloza
Publication date: 01-03-2013
Publisher: Springer-Verlag
Published in: Journal on Data Semantics / Issue 1/2013
Print ISSN: 1861-2032
Electronic ISSN: 1861-2040
DOI: https://doi.org/10.1007/s13740-012-0013-x

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner