A heuristic algorithm for computing the max–min inverse fuzzy relation. (English) Zbl 1033.68138
Summary: The paper addresses a classical problem of computing approximate max–min inverse fuzzy relation. It is an NP-complete problem for which no polynomial time algorithm is known till this date. The paper employs a heuristic function to reduce the search space for finding the solution of the problem. The time-complexity of the proposed algorithm is O(\(n^3\)), compared to O(\(k^n\)), which is required for an exhaustive search in the real space of [0,1] at \(k\) regular intervals of interval length (\(1/k\)).
MSC:
| 68W05 | Nonnumerical algorithms |
References:
| [1] | Arnould, T.; Tano, S., Interval-valued fuzzy backward reasoning, IEEE Trans. Fuzzy Systems, 3, 4, 425-437 (1995) |
| [2] | Arnould, T.; Tano, S.; Kato, Y.; Miyoshi, T., Backward chaining with fuzzy “if…then… rules”, (Proceedings of the Second IEEE International Conference on Fuzzy Systems, San Francisco, CA (1993)), 548-553 |
| [3] | Arnould, T.; Tano, S., The inverse problem of the aggregation of fuzzy sets, Int. J. Uncertainty, Fuzziness Knowledge Based Systems, 2, 4, 391-415 (1994) · Zbl 1232.68123 |
| [4] | Bendes, E. A., Mathematical Methods in Artificial Intelligence (1996), IEE Computer Society Press: IEE Computer Society Press Silver Spring, MD · Zbl 0896.68113 |
| [5] | Drewniak, J., Fuzzy relation inequalities, Cybernet Syst., 88, 677-684 (1988) |
| [6] | Kim, K. H.; Roush, F. W., Generalized fuzzy matrices, Fuzzy Sets and Systems, 4, 293-315 (1980) · Zbl 0451.20055 |
| [7] | Klir, G. J.; Folger, T. A., Fuzzy sets, Uncertainty, and Information (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ, (Chapter 1) · Zbl 0675.94025 |
| [8] | Kosko, B., Fuzzy Engineering (1997), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0895.94015 |
| [9] | Konar, A.; Mondal, A. K., Uncertainty management in expert systems using fuzzy petri nets, IEEE Trans. Knowledge Data Eng., 8, 1, 96-105 (1996) |
| [10] | Pappis, C. P.; Adamopoulos, G. I., A computer algorithm for the solution of the inverse problem of fuzzy systems, Fuzzy Sets and Systems, 39, 279-290 (1991) · Zbl 0727.93029 |
| [11] | Pedrycz, W., Inverse problem in fuzzy relational equations, Fuzzy Sets and Systems, 36, 277-291 (1990) · Zbl 0708.04003 |
| [12] | Rich, E.; Knight, K., Artificial Intelligence (1991), McGraw-Hill: McGraw-Hill New York |
| [13] | Ross, T. J., Fuzzy Logic with Engineering Applications (1995), McGraw-Hill: McGraw-Hill New York · Zbl 0855.93003 |
| [14] | P. Saha, Abductive Reasoning with Inverse Fuzzy Discrete Relations, Ph.D. dissertation, Jadavpur University, India, 2002; P. Saha, Abductive Reasoning with Inverse Fuzzy Discrete Relations, Ph.D. dissertation, Jadavpur University, India, 2002 |
| [15] | Sanchez, E., Resolution of composite fuzzy relation equations, Inf. Control, 30, 38-48 (1976) · Zbl 0326.02048 |
| [16] | Sanchez, E., Solution of fuzzy equations with extended operations, Fuzzy Sets and Systems, 12, 237-247 (1984) · Zbl 0556.04001 |
| [17] | Zadeh, L. A., Knowledge representation in fuzzy logic, IEEE Trans. Knowledge Data Eng., 1, 1 (1988) · Zbl 0634.03020 |
| [18] | H.J. Zimmerman, Fuzzy Set Theory and its Applications, Kluwer Academic Publishers, Dordrecht; H.J. Zimmerman, Fuzzy Set Theory and its Applications, Kluwer Academic Publishers, Dordrecht · Zbl 0845.04006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
