×

On the failure of the finite model property in some fuzzy description logics. (English) Zbl 1231.03025

Summary: Fuzzy Description Logics (DLs) are a family of logics which allow the representation of (and the reasoning with) structured knowledge affected by vagueness. Although most of the not very expressive crisp DLs, such as \(\mathcal {ALC}\), enjoy the Finite Model Property (FMP), this is not the case once we move into the fuzzy case. In this paper we show that if we allow arbitrary knowledge bases, then the fuzzy DLs \(\mathcal {ALC}\) under Łukasiewicz and product fuzzy logics do not verify the FMP even if we restrict the models to witnessed models; in other words, finite satisfiability and witnessed satisfiability are different for arbitrary knowledge bases. The aim of this paper is to point out the failure of FMP because it affects several algorithms published in the literature for reasoning under fuzzy DLs.

MSC:

03B52 Fuzzy logic; logic of vagueness
68T27 Logic in artificial intelligence
68T30 Knowledge representation
68T37 Reasoning under uncertainty in the context of artificial intelligence

Software:

Fuzzydl
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aguzzoli, S., The complexity of McNaughton functions of one variable, Advances in Applied Mathematics, 21, 1, 58-77 (1998) · Zbl 0911.03004
[2] Baader, F.; Calvanese, D.; McGuinness, D.; Nardi, D.; Patel-Schneider, P. F., The Description Logic Handbook: Theory, Implementation, and Applications (2003), Cambridge University Press · Zbl 1058.68107
[3] Baader, F.; Franconi, E.; Hollunder, B.; Nebel, B.; Profitlich, H.-J., An empirical analysis of optimization techniques for terminological representation systems or: making KRIS get a move on, Applied Artificial Intelligence, 4, 109-132 (1994)
[4] F. Baader, I. Horrocks, U. Sattler, Description logics as ontology languages for the semantic web, in: D. Hutter, W. Stephan (Eds.), Mechanizing Mathematical Reasoning: Essays in Honor of Jörg H. Siekmann on the Occasion of His 60th Birthday, Lecture Notes in Artificial Intelligence, vol. 2605, Springer-Verlag, 2005, pp. 228-248.; F. Baader, I. Horrocks, U. Sattler, Description logics as ontology languages for the semantic web, in: D. Hutter, W. Stephan (Eds.), Mechanizing Mathematical Reasoning: Essays in Honor of Jörg H. Siekmann on the Occasion of His 60th Birthday, Lecture Notes in Artificial Intelligence, vol. 2605, Springer-Verlag, 2005, pp. 228-248. · Zbl 1098.68705
[5] Blackburn, P.; de Rijke, M.; Venema, Y., Modal Logic (2001), Cambridge University Press · Zbl 0988.03006
[6] F. Bobillo, U. Straccia, A fuzzy description logic with product t-norm, in: Proceedings of the 16th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2007), IEEE Press, 2007, pp. 652-657.; F. Bobillo, U. Straccia, A fuzzy description logic with product t-norm, in: Proceedings of the 16th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2007), IEEE Press, 2007, pp. 652-657.
[7] Bobillo, F.; Straccia, U., Fuzzy description logics with general t-norms and datatypes, Fuzzy Sets and Systems, 160, 23, 3382-3402 (2009) · Zbl 1192.68659
[8] F. Bobillo, U. Straccia, FuzzyDL: an expressive fuzzy description logic reasoner, in: Proceedings of the 17th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2008), IEEE Computer Society, 2008, pp. 923-930.; F. Bobillo, U. Straccia, FuzzyDL: an expressive fuzzy description logic reasoner, in: Proceedings of the 17th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2008), IEEE Computer Society, 2008, pp. 923-930.
[9] F. Bobillo, U. Straccia, On qualified cardinality restrictions in fuzzy description logics under Łukasiewicz semantics, in: Proceedings of the 12th International Conference of Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2008), 2008, pp. 1008-1015.; F. Bobillo, U. Straccia, On qualified cardinality restrictions in fuzzy description logics under Łukasiewicz semantics, in: Proceedings of the 12th International Conference of Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2008), 2008, pp. 1008-1015.
[10] Cuenca-Grau, B.; Horrocks, I.; Motik, B.; Parsia, B.; Patel-Schneider, P.; Sattler, U., OWL 2: the next step for OWL, Journal of Web Semantics, 6, 4, 309-322 (2008)
[11] García-Cerdaña, À.; Armengol, E.; Esteva, F., Fuzzy description logics and t-norm based fuzzy logics, International Journal of Approximate Reasoning, 51, 6, 632-655 (2010) · Zbl 1209.68522
[12] Hájek, P., Computational complexity of t-norm based propositional fuzzy logics with rational truth constants, Fuzzy Sets and Systems, 157, 5, 677-682 (2006) · Zbl 1104.03015
[13] Hájek, P., Making fuzzy description logic more general, Fuzzy Sets and Systems, 154, 1, 1-15 (2005) · Zbl 1094.03014
[14] Hájek, P., Metamathematics of Fuzzy Logic (1998), Kluwer · Zbl 0937.03030
[15] Hájek, P., On witnessed models in fuzzy logic, Mathematical Logic Quarterly, 53, 1, 66-77 (2007) · Zbl 1110.03013
[16] Lukasiewicz, T.; Straccia, U., Managing uncertainty and vagueness in description logics for the semantic web, Journal of Web Semantics, 6, 4, 291-308 (2008)
[17] B. Nebel, Reasoning and revision in hybrid representation systems, in: Lecture Notes in Artificial Intelligence, vol. 422, Springer-Verlag, 1990, pp. 228-248.; B. Nebel, Reasoning and revision in hybrid representation systems, in: Lecture Notes in Artificial Intelligence, vol. 422, Springer-Verlag, 1990, pp. 228-248. · Zbl 0702.68095
[18] K. Schild, A correspondence theory for terminological logics: preliminary report, in: Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI 1991), Morgan Kaufmann, 1991, pp. 466-471.; K. Schild, A correspondence theory for terminological logics: preliminary report, in: Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI 1991), Morgan Kaufmann, 1991, pp. 466-471. · Zbl 0742.68059
[19] Schmidt-Schauß, M.; Smolka, G., Attributive concept descriptions with complements, Artificial Intelligence, 48, 1, 1-26 (1991) · Zbl 0712.68095
[20] G. Stoilos, G. Stamou, A framework for reasoning with expressive continuous fuzzy description logics, in: Proceedings of the 22nd International Workshop on Description Logics (DL 2009), CEUR Workshop Proceedings, 2009.; G. Stoilos, G. Stamou, A framework for reasoning with expressive continuous fuzzy description logics, in: Proceedings of the 22nd International Workshop on Description Logics (DL 2009), CEUR Workshop Proceedings, 2009.
[21] U. Straccia, A fuzzy description logic for the semantic web, in: E. Sanchez (Ed.), Fuzzy Logic and the Semantic Web, Capturing Intelligence, vol. 1, Elsevier Science, 2006, pp. 73-90.; U. Straccia, A fuzzy description logic for the semantic web, in: E. Sanchez (Ed.), Fuzzy Logic and the Semantic Web, Capturing Intelligence, vol. 1, Elsevier Science, 2006, pp. 73-90.
[22] Straccia, U., Reasoning within fuzzy description logics, Journal of Artificial Intelligence Research, 14, 137-166 (2001) · Zbl 0973.03034
[23] U. Straccia, F. Bobillo, Mixed integer programming, general concept inclusions and fuzzy description logics, in: Proceedings of the 5th Conference of the European Society for Fuzzy Logic and Technology (EUSFLAT 2007), vol. 2, 2007, pp. 213-220.; U. Straccia, F. Bobillo, Mixed integer programming, general concept inclusions and fuzzy description logics, in: Proceedings of the 5th Conference of the European Society for Fuzzy Logic and Technology (EUSFLAT 2007), vol. 2, 2007, pp. 213-220. · Zbl 1152.68632
[24] Straccia, U.; Bobillo, F., Mixed integer programming, general concept inclusions and fuzzy description logics, Mathware & Soft Computing, 14, 3, 247-259 (2007) · Zbl 1152.68632
[25] Zadeh, L. A., Fuzzy sets, Information and Control, 8, 338-353 (1965) · Zbl 0139.24606
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.