| Title:
|
On the resolution of bipolar max-min equations (English) |
| Author:
|
Li, Pingke |
| Author:
|
Jin, Qingwei |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
52 |
| Issue:
|
4 |
| Year:
|
2016 |
| Pages:
|
514-530 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
bipolar max-min equations |
| Keyword:
|
fuzzy relational equations |
| Keyword:
|
satisfiability |
| Keyword:
|
linear inequalities |
| MSC:
|
49M37 |
| MSC:
|
90C70 |
| idZBL:
|
Zbl 06644308 |
| idMR:
|
MR3565767 |
| DOI:
|
10.14736/kyb-2016-4-0514 |
| . |
| Date available:
|
2016-10-20T08:04:26Z |
| Last updated:
|
2018-01-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145903 |
| . |
| Reference:
|
[1] Crama, Y., Hammer, P.: Boolean Functions: Theory, Algorithms, and Applications..Cambridge University Press, Cambridge 2011. Zbl 1237.06001, MR 2742439 |
| Reference:
|
[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. Zbl 0970.03044, MR 1890236, 10.1007/978-1-4615-4429-6_7 |
| Reference:
|
[3] Nola, A. Di, Sessa, S., Pedrycz, W., Sanchez, E.: Fuzzy Relation Equations and Their Applications to Knowledge Engineering..Kluwer, Dordrecht 1989. Zbl 0694.94025, MR 1120025, 10.1007/978-94-017-1650-5 |
| Reference:
|
[4] Freson, S., Baets, B. De, Meyer, H. De: Linear optimization with bipolar max-min constraints..Inform. Sci. 234 (2013), 3-15. Zbl 1284.90104, MR 3039624, 10.1016/j.ins.2011.06.009 |
| Reference:
|
[5] Johnson, D. S., Yannakakis, M., Papadimitriou, C. H.: On generating all maximal independent sets..Inform. Process. Lett. 27 (1988), 119-123. Zbl 0654.68086, MR 0933271, 10.1016/0020-0190(88)90065-8 |
| Reference:
|
[6] Li, P.: Fuzzy Relational Equations: Resolution and Optimization..Ph.D. Dissertation, North Carolina State University, 2009. |
| Reference:
|
[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. Zbl 1169.90493, MR 2403173, 10.1007/s10700-008-9029-y |
| Reference:
|
[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. MR 2511474, 10.1007/s10700-009-9059-0 |
| Reference:
|
[9] Li, P., Jin, Q.: Fuzzy relational equations with min-biimplication composition..Fuzzy Optim. Decision Making 11 (2012), 227-240. Zbl 1254.03101, MR 2923611, 10.1007/s10700-012-9122-0 |
| Reference:
|
[10] Palopoli, L., Pirri, F., Pizzuti, C.: Algorithms for selective enumeration of prime implicants..Artificial Intelligence 111 (1999), 41-72. Zbl 0996.68181, MR 1711469, 10.1016/s0004-3702(99)00035-1 |
| Reference:
|
[11] Peeva, K., Kyosev, Y.: Fuzzy Relational Calculus: Theory, Applications and Software..World Scientific, New Jersey 2004. Zbl 1083.03048, MR 2379415, 10.1142/5683 |
| . |
