On the resolution of bipolar max-min equations

Pingke Li; Qingwei Jin

Kybernetika (2016)

  • Volume: 52, Issue: 4, page 514-530
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Li, Pingke, and Jin, Qingwei. "On the resolution of bipolar max-min equations." Kybernetika 52.4 (2016): 514-530. <http://eudml.org/doc/286830>.

@article{Li2016,
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.},
author = {Li, Pingke, Jin, Qingwei},
journal = {Kybernetika},
keywords = {bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities; bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities},
language = {eng},
number = {4},
pages = {514-530},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On the resolution of bipolar max-min equations},
url = {http://eudml.org/doc/286830},
volume = {52},
year = {2016},
}

TY - JOUR
AU - Li, Pingke
AU - Jin, Qingwei
TI - On the resolution of bipolar max-min equations
JO - Kybernetika
PY - 2016
PB - Institute of Information Theory and Automation AS CR
VL - 52
IS - 4
SP - 514
EP - 530
AB - 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.
LA - eng
KW - bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities; bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities
UR - http://eudml.org/doc/286830
ER -

References

top
  1. Crama, Y., Hammer, P., Boolean Functions: Theory, Algorithms, and Applications., Cambridge University Press, Cambridge 2011. Zbl1237.06001MR2742439
  2. Baets, B. De, 10.1007/978-1-4615-4429-6_7, 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. Zbl0970.03044MR1890236DOI10.1007/978-1-4615-4429-6_7
  3. Nola, A. Di, Sessa, S., Pedrycz, W., Sanchez, E., 10.1007/978-94-017-1650-5, Kluwer, Dordrecht 1989. Zbl0694.94025MR1120025DOI10.1007/978-94-017-1650-5
  4. Freson, S., Baets, B. De, Meyer, H. De, 10.1016/j.ins.2011.06.009, Inform. Sci. 234 (2013), 3-15. Zbl1284.90104MR3039624DOI10.1016/j.ins.2011.06.009
  5. Johnson, D. S., Yannakakis, M., Papadimitriou, C. H., 10.1016/0020-0190(88)90065-8, Inform. Process. Lett. 27 (1988), 119-123. Zbl0654.68086MR0933271DOI10.1016/0020-0190(88)90065-8
  6. Li, P., Fuzzy Relational Equations: Resolution and Optimization., Ph.D. Dissertation, North Carolina State University, 2009. 
  7. Li, P., Fang, S.-C., 10.1007/s10700-008-9029-y, Fuzzy Optim. Decision Making 7 (2008), 169-214. Zbl1169.90493MR2403173DOI10.1007/s10700-008-9029-y
  8. Li, P., Fang, S.-C., 10.1007/s10700-009-9059-0, Fuzzy Optim. Decision Making 8 (2009), 179-229. MR2511474DOI10.1007/s10700-009-9059-0
  9. Li, P., Jin, Q., 10.1007/s10700-012-9122-0, Fuzzy Optim. Decision Making 11 (2012), 227-240. Zbl1254.03101MR2923611DOI10.1007/s10700-012-9122-0
  10. Palopoli, L., Pirri, F., Pizzuti, C., 10.1016/s0004-3702(99)00035-1, Artificial Intelligence 111 (1999), 41-72. Zbl0996.68181MR1711469DOI10.1016/s0004-3702(99)00035-1
  11. Peeva, K., Kyosev, Y., 10.1142/5683, World Scientific, New Jersey 2004. Zbl1083.03048MR2379415DOI10.1142/5683

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.