Kybernetika 52 no. 4, 514-530, 2016

On the resolution of bipolar max-min equations

Pingke Li and Qingwei JinDOI: 10.14736/kyb-2016-4-0514

Abstract:

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.

Keywords:

linear inequalities, bipolar max-min equations, fuzzy relational equations, satisfiability

Classification:

90C70, 49M37

paper.pdf

References:

  1. Y. Crama and P. Hammer: Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, Cambridge 2011.   CrossRef
  2. B. De Baets: 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
  3. A. Di Nola, S. Sessa, W. Pedrycz and E. Sanchez: Fuzzy Relation Equations and Their Applications to Knowledge Engineering. Kluwer, Dordrecht 1989.   DOI:10.1007/978-94-017-1650-5
  4. S. Freson, B. De Baets and H. De Meyer: Linear optimization with bipolar max-min constraints. Inform. Sci. 234 (2013), 3-15.   DOI:10.1016/j.ins.2011.06.009
  5. D. S. Johnson, M. Yannakakis and C. H. Papadimitriou: On generating all maximal independent sets. Inform. Process. Lett. 27 (1988), 119-123.   DOI:10.1016/0020-0190(88)90065-8
  6. P. Li: Fuzzy Relational Equations: Resolution and Optimization. Ph.D. Dissertation, North Carolina State University, 2009.   CrossRef
  7. P. Li and S.-C. Fang: 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
  8. P. Li and S.-C. Fang: 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
  9. P. Li and Q. Jin: Fuzzy relational equations with min-biimplication composition. Fuzzy Optim. Decision Making 11 (2012), 227-240.   DOI:10.1007/s10700-012-9122-0
  10. L. Palopoli, F. Pirri and C. Pizzuti: Algorithms for selective enumeration of prime implicants. Artificial Intelligence 111 (1999), 41-72.   DOI:10.1016/s0004-3702(99)00035-1
  11. K. Peeva and Y. Kyosev: Fuzzy Relational Calculus: Theory, Applications and Software. World Scientific, New Jersey 2004.   DOI:10.1142/5683