Geodesic
On the resolution of bipolar max-min equations
Kybernetika, Tome 52 (2016) no. 4, pp. 514-530
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2016-4-0514
Classification : 49M37, 90C70
Keywords: bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities 
@article{10_14736_kyb_2016_4_0514,
     author = {Li, Pingke and Jin, Qingwei},
     title = {On the resolution of bipolar max-min equations},
     journal = {Kybernetika},
     pages = {514--530},
     year = {2016},
     volume = {52},
     number = {4},
     doi = {10.14736/kyb-2016-4-0514},
     mrnumber = {3565767},
     zbl = {06644308},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-4-0514/}
}
TY  - JOUR
AU  - Li, Pingke
AU  - Jin, Qingwei
TI  - On the resolution of bipolar max-min equations
JO  - Kybernetika
PY  - 2016
SP  - 514
EP  - 530
VL  - 52
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-4-0514/
DO  - 10.14736/kyb-2016-4-0514
LA  - en
ID  - 10_14736_kyb_2016_4_0514
ER  - 
%0 Journal Article
%A Li, Pingke
%A Jin, Qingwei
%T On the resolution of bipolar max-min equations
%J Kybernetika
%D 2016
%P 514-530
%V 52
%N 4
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-4-0514/
%R 10.14736/kyb-2016-4-0514
%G en
%F 10_14736_kyb_2016_4_0514
Li, Pingke; Jin, Qingwei. On the resolution of bipolar max-min equations. Kybernetika, Tome 52 (2016) no. 4, pp. 514-530. doi: 10.14736/kyb-2016-4-0514

[1] Crama, Y., Hammer, P.: Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, Cambridge 2011. | MR | Zbl

[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 | MR | Zbl

[3] Nola, A. Di, Sessa, S., Pedrycz, W., Sanchez, E.: Fuzzy Relation Equations and Their Applications to Knowledge Engineering. Kluwer, Dordrecht 1989. | DOI | MR | Zbl

[4] Freson, S., Baets, B. De, Meyer, H. De: Linear optimization with bipolar max-min constraints. Inform. Sci. 234 (2013), 3-15. | DOI | MR | Zbl

[5] Johnson, D. S., Yannakakis, M., Papadimitriou, C. H.: On generating all maximal independent sets. Inform. Process. Lett. 27 (1988), 119-123. | DOI | MR | Zbl

[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 | MR | Zbl

[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 | MR

[9] Li, P., Jin, Q.: Fuzzy relational equations with min-biimplication composition. Fuzzy Optim. Decision Making 11 (2012), 227-240. | DOI | MR | Zbl

[10] Palopoli, L., Pirri, F., Pizzuti, C.: Algorithms for selective enumeration of prime implicants. Artificial Intelligence 111 (1999), 41-72. | DOI | MR | Zbl

[11] Peeva, K., Kyosev, Y.: Fuzzy Relational Calculus: Theory, Applications and Software. World Scientific, New Jersey 2004. | DOI | MR | Zbl

Cité par Sources :