On the relation between equations with max-product composition and the covering problem.

*(English)*Zbl 1073.03538Summary: Systems of equations with max-product composition are considered. It is shown that solving these equations is closely related with the covering problem, which belongs to the category of NP-hard problems. It is proved that minimal solutions of equations correspond to irredundant coverings. In terms of the covering problem the conditions of compatibility of equations, of redundancy of equations, of uniqueness of solution, of uniqueness of minimal solution are determined. Concepts of essential, non-essential, semi-essential and super-essential variables are suggested. Ways of simplification of a covering problem and methods of solving it are considered.

##### MSC:

03E72 | Theory of fuzzy sets, etc. |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

##### Keywords:

Fuzzy relations; Fuzzy relation equations; Inverse problem; Max-product composition; Minimal solutions; Covering problem; NP-hard problems; NP-complete problems
PDF
BibTeX
XML
Cite

\textit{A. V. Markovskii}, Fuzzy Sets Syst. 153, No. 2, 261--273 (2005; Zbl 1073.03538)

Full Text:
DOI

##### References:

[1] | Bourke, M.; Fisher, D., Solution algorithms for fuzzy relational equations with MAX-product composition, Fuzzy sets and systems, 94, 61-69, (1998) · Zbl 0923.04003 |

[2] | Cormen, T.; Leiserson, C.; Rivest, R., Introduction to algorithms, (1990), MIT Press Cambridge |

[3] | De Baets, B., Analytical solution methods for fuzzy relational equations, (), 291-340 · Zbl 0970.03044 |

[4] | Di Nola, A.; Sanchez, E.; Pedrycz, W.; Sessa, S., Fuzzy relation equations and their applications to knowledge engineering, (1989), Kluwer Academic Publishers Norwell, MA · Zbl 0694.94025 |

[5] | M. Garey, D. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completness, W.H. Freeman, San Francisco, 1979. · Zbl 0411.68039 |

[6] | Loetamonphong, J.; Fang, S.-Ch., Optimization of fuzzy equation with MAX-product composition, Fuzzy sets and systems, 118, 509-517, (2001) · Zbl 1044.90533 |

[7] | Pappis, C.; Sugeno, M., Fuzzy relational equations and the inverse problem, Fuzzy sets and systems, 15, 1, 79-90, (1985) · Zbl 0561.04003 |

[8] | Peeva, K., Fuzzy linear systems, Fuzzy sets and systems, 49, 3, 339-355, (1992) · Zbl 0805.04005 |

[9] | Peeva, E., Finite L-fuzzy machines, Fuzzy sets and systems, 141, 3, 415-437, (2004) · Zbl 1059.68066 |

[10] | Sanches, E., Resolution of composite fuzzy relation equations, Inf. control, 30, 38-48, (1976) |

[11] | Wagenknecht, M.; Hartmann, K., Application of fuzzy sets of type-2 to the solution of fuzzy equation systems, Fuzzy sets and systems, 25, 183-190, (1988) · Zbl 0651.04006 |

[12] | Wagenknecht, M.; Hartmann, K., On the existence of minimal solutions for fuzzy equations with tolerances, Fuzzy sets and systems, 34, 237-244, (1990) · Zbl 0687.90094 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.