Previous |  Up |  Next


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:
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


Files Size Format View
Kybernetika_52-2016-4_2.pdf 342.6Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo