Fuzzy relational equations with min-biimplication composition. (English) Zbl 1254.03101

Summary: We discuss fuzzy relational equations with min-biimplication composition where the biimplication is the biresiduation operation with respect to the Łukasiewicz t-norm. It is shown that determining whether a finite system of fuzzy relational equations with min-biimplication composition has a solution is NP-complete. Moreover, a system of such equations can be fully characterized by a system of integer linear inequalities and consequently its solution set can be expressed in the terms of the minimal solutions of this system of integer linear inequalities.


03E72 Theory of fuzzy sets, etc.
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)


Full Text: DOI


[1] Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds) (2009) Handbook of satisfiability. IOS Press, Amsterdam · Zbl 1183.68568
[2] Chandra A. K., Markowsky G. (1978) On the number of prime implicants. Discrete Mathematics 24: 7–11 · Zbl 0392.03038
[3] Crama Y., Hammer P. (2011) Boolean functions: Theory, algorithms, and applications. Cambridge University Press, Cambridge · Zbl 1237.06001
[4] De Baets B. (2000) Analytical solution methods for fuzzy relational equations. In: Dubois D., Prade H. (eds) Fundamentals of fuzzy sets, The handbooks of fuzzy sets series (Vol. 1). Kluwer, Dordrecht, pp 291–340 · Zbl 0970.03044
[5] Di Nola A., Pedrycz W., Sessa S. (1988) Fuzzy relation equations with equality and difference composition operations. Fuzzy Sets and Systems 25: 205–215 · Zbl 0645.04004
[6] Di Nola A., Pedrycz W., Sessa S. (1990) Modus ponens for fuzzy data realized via equations with equality operators. International Journal of Intelligent Systems 5: 1–14 · Zbl 0703.03005
[7] Di Nola A., Sessa S., Pedrycz W. (1990) On some finite fuzzy relation equations. Information Sciences 50: 93–109 · Zbl 0688.90002
[8] Di Nola A., Sessa S., Pedrycz W., Sanchez E. (1989) Fuzzy relation equations and their applications to knowledge engineering. Kluwer, Dordrecht · Zbl 0694.94025
[9] Johnson D. S., Yannakakis M., Papadimitriou C. H. (1988) On generating all maximal independent sets. Information Processing Letters 27: 119–123 · Zbl 0654.68086
[10] Klawonn F., Gebhardt J., Kruse R. (1995) Fuzzy control on the basis of equality relations with an example from idle speed control. IEEE Transactions on Fuzzy Systems 3: 336–349
[11] Klawonn F., Kruse R. (1993) Equality relations as a basis for fuzzy control. Fuzzy Sets and Systems 54: 147–156 · Zbl 0785.93059
[12] Klement E. P., Mesiar R., Pap E. (2000) Triangular norms. Kluwer, Dordrecht
[13] Li, P. (2009). Fuzzy relational equations: Resolution and optimization, Ph.D. Dissertation, North Carolina State University.
[14] Li P., Fang S. -C. (2008) On the resolution and optimization of a system of fuzzy relational equations with sup-T composition. Fuzzy Optimization and Decision Making 7: 169–214 · Zbl 1169.90493
[15] Li P., Fang S. -C. (2009) A survey on fuzzy relational equations, Part I: Classification and solvability. Fuzzy Optimization and Decision Making 8: 179–229 · Zbl 1180.03051
[16] Liu W. J., Wang X. P. (1989) Biimplication operator and its application on fuzzy relation equation. BUSEFAL 41: 31–40
[17] Moser B. (2006) On the T-transitivity of kernels. Fuzzy Sets and Systems 157: 1787–1796 · Zbl 1100.68095
[18] Moser B. (2006) On representing and generating kernels by fuzzy equivalence relations. Journal of Machine Learning Research 7: 2603–2620 · Zbl 1222.68269
[19] Palopoli L., Pirri F., Pizzuti C. (1999) Algorithms for selective enumeration of prime implicants. Artificial Intelligence 111: 41–72 · Zbl 0996.68181
[20] Peeva K., Kyosev Y. (2004) Fuzzy relational calculus: Theory, applications and software. World Scientific, New Jersey · Zbl 1083.03048
[21] Perfilieva I., Novák V. (2007) System of fuzzy relation equations as a continuous model of IF-THEN rules. Information Sciences 177: 3218–3227 · Zbl 1124.03029
[22] Recasens J. (2010) Indistinguishability operators: Modelling fuzzy equalities and fuzzy equivalence relations. Springer, Heidelberg · Zbl 1215.03065
[23] Sanchez E. (1976) Resolution of composite fuzzy relation equation. Information and Control 30: 38–48 · Zbl 0326.02048
[24] Sanchez E. (1977) Solutions in composite fuzzy relation equations: Application to medical diagnosis in Brouwerian logic. In: Gupta M. M., Saridis G. N., Gaines B. R. (eds) Fuzzy automata and decision processes. North-Holland, Amsterdam, pp 221–234
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.