Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities
bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities
Summary:
This paper investigates bipolar max-min equations which can be viewed as a generalization of fuzzy relational equations with max-min composition. The relation between the consistency of bipolar max-min equations and the classical boolean satisfiability problem is revealed. Consequently, it is shown that the problem of determining whether a system of bipolar max-min equations is consistent or not is NP-complete. Moreover, a consistent system of bipolar max-min equations, as well as its solution set, can be fully characterized by a system of integer linear inequalities.
References:
[1] Crama, Y., Hammer, P.: Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, Cambridge 2011. MR 2742439 | Zbl 1237.06001
[2] Baets, B. De: Analytical solution methods for fuzzy relational equations. In: Fundamentals of Fuzzy Sets, The Handbooks of Fuzzy Sets Series, Vol. 1 (D. Dubois and H. Prade, eds.), Kluwer, Dordrecht 2000, pp. 291-340. DOI 10.1007/978-1-4615-4429-6_7 | MR 1890236 | Zbl 0970.03044
[3] Nola, A. Di, Sessa, S., Pedrycz, W., Sanchez, E.: Fuzzy Relation Equations and Their Applications to Knowledge Engineering. Kluwer, Dordrecht 1989. DOI 10.1007/978-94-017-1650-5 | MR 1120025 | Zbl 0694.94025
[4] Freson, S., Baets, B. De, Meyer, H. De: Linear optimization with bipolar max-min constraints. Inform. Sci. 234 (2013), 3-15. DOI 10.1016/j.ins.2011.06.009 | MR 3039624 | Zbl 1284.90104
[5] Johnson, D. S., Yannakakis, M., Papadimitriou, C. H.: On generating all maximal independent sets. Inform. Process. Lett. 27 (1988), 119-123. DOI 10.1016/0020-0190(88)90065-8 | MR 0933271 | Zbl 0654.68086
[6] Li, P.: Fuzzy Relational Equations: Resolution and Optimization. Ph.D. Dissertation, North Carolina State University, 2009.
[7] Li, P., Fang, S.-C.: On the resolution and optimization of a system of fuzzy relational equations with sup-$T$ composition. Fuzzy Optim. Decision Making 7 (2008), 169-214. DOI 10.1007/s10700-008-9029-y | MR 2403173 | Zbl 1169.90493
[8] Li, P., Fang, S.-C.: A survey on fuzzy relational equations, Part I: Classification and solvability. Fuzzy Optim. Decision Making 8 (2009), 179-229. DOI 10.1007/s10700-009-9059-0 | MR 2511474
[9] Li, P., Jin, Q.: Fuzzy relational equations with min-biimplication composition. Fuzzy Optim. Decision Making 11 (2012), 227-240. DOI 10.1007/s10700-012-9122-0 | MR 2923611 | Zbl 1254.03101
[10] Palopoli, L., Pirri, F., Pizzuti, C.: Algorithms for selective enumeration of prime implicants. Artificial Intelligence 111 (1999), 41-72. DOI 10.1016/s0004-3702(99)00035-1 | MR 1711469 | Zbl 0996.68181
[11] Peeva, K., Kyosev, Y.: Fuzzy Relational Calculus: Theory, Applications and Software. World Scientific, New Jersey 2004. DOI 10.1142/5683 | MR 2379415 | Zbl 1083.03048
Search
Partner of
