Computing sets of graded attribute implications with witnessed non-redundancy. (English) Zbl 1398.68560

Summary: In this paper we extend our previous results on sets of graded attribute implications with witnessed non-redundancy. We assume finite residuated lattices as structures of truth degrees and use arbitrary idempotent truth-stressing linguistic hedges as parameters which influence the semantics of graded attribute implications. In this setting, we introduce algorithm which transforms any set of graded attribute implications into an equivalent non-redundant set of graded attribute implications with saturated consequents whose non-redundancy is witnessed by antecedents of the formulas. As a consequence, we solve the open problem regarding the existence of general systems of pseudo-intents which appear in formal concept analysis of object-attribute data with graded attributes and linguistic hedges. Furthermore, we show a polynomial-time procedure for determining bases given by general systems of pseudo-intents from sets of graded attribute implications which are complete in data.


68T37 Reasoning under uncertainty in the context of artificial intelligence
03B52 Fuzzy logic; logic of vagueness
06F05 Ordered semigroups and monoids
68T30 Knowledge representation
Full Text: DOI arXiv


[1] Armstrong, W. W., Dependency structures of data base relationships, (Rosenfeld, J. L.; Freeman, H., Proceedings of the 1974 IFIP Congress on Information Processing, (1974), North Holland Amsterdam), 580-583 · Zbl 0296.68038
[2] Belohlavek, R., Fuzzy Relational Systems: Foundations and Principles, (2002), Kluwer Academic Publishers Norwell, MA, USA · Zbl 1067.03059
[3] Belohlavek, R.; Chlupova, M.; Vychodil, V., Implications from data with fuzzy attributes, Proceedings of the 2004 IEEE International Conference on Advances in Intelligent Systems - Theory and Applications, 5, (2004), University of Canberra, Centre de Recherche Public Henri Tudor
[4] Belohlavek, R.; Cordero, P.; Enciso, M.; Mora, A.; Vychodil, V., An efficient reasoning method for dependencies over similarity and ordinal data, (Torra, V.; Narukawa, Y.; López, B.; Villaret, M., Modeling Decisions for Artificial Intelligence, Lecture Notes in Computer Science, vol. 7647, (2012), Springer Berlin Heidelberg), 408-419
[5] Belohlavek, R.; Funiokova, T.; Vychodil, V., Fuzzy closure operators with truth stressers, Logic J. IGPL, 13, 5, 503-513, (2005) · Zbl 1089.06001
[6] Belohlavek, R.; Vychodil, V., Fuzzy attribute implications: computing non-redundant bases using maximal independent sets, (Zhang, S.; Jarvis, R., AI 2005: Advances in Artificial Intelligence, Lecture Notes in Computer Science, vol. 3809, (2005), Springer Berlin Heidelberg), 1126-1129 · Zbl 1175.68448
[7] Belohlavek, R.; Vychodil, V., Fuzzy attribute logic: attribute implications, their validity, entailment, and non-redundant basis, Fuzzy Logic, Soft Computing & Computational Intelligence: Eleventh International Fuzzy Systems Association World Congress, 622-627, (2005), Tsinghua University Press and Springer
[8] Belohlavek, R.; Vychodil, V., Reducing the size of fuzzy concept lattices by hedges, Proceedings of the Fourteenth IEEE International Conference on Fuzzy Systems, 663-668, (2005)
[9] Belohlavek, R., Attribute implications in a fuzzy setting, (Vychodil, V.; Missaoui, R.; Schmidt, J., Formal Concept Analysis, Lecture Notes in Computer Science, vol. 3874, (2006), Springer Berlin Heidelberg), 45-60 · Zbl 1177.68203
[10] Belohlavek, R.; Vychodil, V., Computing non-redundant bases of if-then rules from data tables with graded attributes, Proceedings of the 2006 IEEE International Conference on Granular Computing (GrC 2006), 205-210, (2006), IEEE
[11] Belohlavek, R.; Vychodil, V., Data tables with similarity relations: functional dependencies, complete rules and non-redundant bases, (Lee, M.; Tan, K.-L.; Wuwongse, V., Database Systems for Advanced Applications, Lecture Notes in Computer Science, vol. 3882, (2006), Springer Berlin Heidelberg), 644-658
[12] Belohlavek, R.; Vychodil, V., Properties of models of fuzzy attribute implications, Proceedings of the Third SCIS & ISIS Joint International Conference on Soft Computing and Intelligent Systems and Seventh International Symposium on advanced Intelligent Systems, 291-296, (2006), Tokyo Institute of Technology, Japan Society for Fuzzy Theory and Intelligent Informatics
[13] Belohlavek, R.; Vychodil, V., On proofs and rule of multiplication in fuzzy attribute logic, (Melin, P.; Castillo, O.; Aguilar, T.; J. Kacprzyk, L.; Pedrycz, W., Foundations of Fuzzy Logic and Soft Computing, Lecture Notes in Computer Science, vol. 4529, (2007), Springer Berlin Heidelberg), 471-480 · Zbl 1202.03036
[14] Belohlavek, R.; Vychodil, V., Query systems in similarity-based databases: logical foundations, expressive power, and completeness, Proceedings of the 2010 ACM Symposium on Applied Computing (SAC ’10), 1648-1655, (2010), ACM New York, NY, USA
[15] Belohlavek, R.; Vychodil, V., Formal concept analysis and linguistic hedges, Int. J. Gen. Syst., 41, 5, 503-532, (2012) · Zbl 1277.93045
[16] Belohlavek, R.; Vychodil, V., Attribute dependencies for data with grades, CoRR, (2014) · Zbl 1404.68158
[17] Belohlavek, R.; Vychodil, V., A logic of graded attributes, Arch. Math. Log., 54, 7-8, 785-802, (2015) · Zbl 1477.03079
[18] Cintula, P.; Hájek, P., Triangular norm based predicate fuzzy logics, Fuzzy Sets Syst., 161, 3, 311-346, (2010) · Zbl 1200.03020
[19] Distel, F.; Sertkaya, B., On the complexity of enumerating pseudo-intents, Discret. Appl. Math., 159, 6, 450-466, (2011) · Zbl 1214.68387
[20] Esteva, F.; Godo, L., Monoidal t-norm based logic: towards a logic for left-continuous t-norms, Fuzzy Sets Syst., 124, 3, 271-288, (2001) · Zbl 0994.03017
[21] Esteva, F.; Godo, L.s.; Noguera, C., A logical approach to fuzzy truth hedges, Inf. Sci., 232, 366-385, (2013) · Zbl 1293.03014
[22] Galatos, N.; Jipsen, P.; Kowalski, T.; Ono, H., Residuated Lattices: An Algebraic Glimpse at Substructural Logics, vol. 151, (2007), Elsevier Science San Diego, USA · Zbl 1171.03001
[23] Ganter, B., Two basic algorithms in concept analysis, Proceedings of the Eighth International Conference on Formal Concept Analysis (Berlin, Heidelberg), ICFCA’10, 312-340, (2010), Springer-Verlag · Zbl 1274.68484
[24] Ganter, B.; Wille, R., Formal Concept Analysis: Mathematical Foundations, (1997), Springer-Verlag New York, Inc., Secaucus, NJ, USA
[25] Goguen, J. A., L-fuzzy sets, J. Math. Anal. Appl., 18, 1, 145-174, (1967) · Zbl 0145.24404
[26] Goguen, J. A., The logic of inexact concepts, Synthese, 19, 325-373, (1979) · Zbl 0184.00903
[27] Gottwald, S., Mathematical fuzzy logics, Bull. Symb. Log., 14, 2, 210-239, (2008) · Zbl 1144.03023
[28] Guigues, J.-L.; Duquenne, V., Familles minimales d’implications informatives resultant d’un tableau de données binaires, Math. Sci. Hum., 95, 5-18, (1986)
[29] Hájek, P., Metamathematics of Fuzzy Logic, (1998), Kluwer Academic Publishers Dordrecht, The Netherlands · Zbl 0937.03030
[30] Hájek, P., On very true, Fuzzy Sets Syst., 124, 3, 329-333, (2001) · Zbl 0997.03028
[31] Holzer, R., Knowledge acquisition under incomplete knowledge using methods from formal concept analysis: part I, Fund. Inf., 63, 1, 17-39, (2004) · Zbl 1102.68114
[32] Klement, E. P.; Mesiar, R.; Pap, E., Triangular Norms, (2000), Springer · Zbl 0972.03002
[33] Klir, G. J.; Yuan, B., Fuzzy Sets and Fuzzy Logic: Theory and Applications, (1995), Prentice-Hall, Inc. Upper Saddle River, NJ, USA · Zbl 0915.03001
[34] Krajči, S., Cluster based efficient generation of fuzzy concepts, Neural Netw. World, 5, 521-530, (2003)
[35] Kwuida, L., Some open problems in formal concept analysis, ICFCA, (2006)
[36] Maier, D., Theory of Relational Databases, (1983), Computer Science Pr Rockville, MD, USA · Zbl 0519.68082
[37] Medina, J.; Ojeda-Aciego, M.; Ruiz-Calviño, J., Formal concept analysis via multi-adjoint concept lattices, Fuzzy Sets Syst., 160, 2, 130-144, (2009) · Zbl 1187.68589
[38] Pollandt, S., Fuzzy-Begriffe: Formale Begriffsanalyse unscharfer Daten, (1997), Springer
[39] Takeuti, G.; Titani, S., Globalization of intuitionistic set theory, Ann. Pure Appl. Logic, 33, 195-211, (1987) · Zbl 0633.03050
[40] Urbanova, L.; Vychodil, V., Derivation digraphs for dependencies in ordinal and similarity-based data, Inf. Sci., 268, 381-396, (2014) · Zbl 1341.68032
[41] V. Vychodil, Parameterizing the semantics of fuzzy attribute implications by systems of isotone Galois connections, IEEE Trans. Fuzzy Systems. CoRR abs/1410.6960. doi:10.1109/TFUZZ.2015.2470530
[42] Vychodil, V., On minimal sets of graded attribute implications, Inf. Sci., 294, 478-488, (2015) · Zbl 1360.68849
[43] Vychodil, V., On sets of graded attribute implications with witnessed non-redundancy, Inf. Sci., 329, 434-446, (2016) · Zbl 1390.68682
[44] Zadeh, L. A., A fuzzy-set-theoretic interpretation of linguistic hedges, J. Cybern., 2, 3, 4-34, (1972)
[45] Zadeh, L. A., The concept of a linguistic variable and its application to approximate reasoning - I, Inf. Sci., 8, 3, 199-249, (1975) · Zbl 0397.68071
[46] Zadeh, L. A., The concept of a linguistic variable and its application to approximate reasoning - II, Inf. Sci., 8, 4, 301-357, (1975) · Zbl 0404.68074
[47] Zadeh, L. A., The concept of a linguistic variable and its application to approximate reasoning - III, Inf. Sci., 9, 1, 43-80, (1975) · Zbl 0404.68075
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.