On the relation between fuzzy max-Archimedean t-norm relational equations and the covering problem

The problem of solving a system of fuzzy relational equations with max-Archimedean t-norm composition is studied. It is shown that this problem is closely related to the covering problem, which belongs to the class of NP-hard problems. It is proved that there is a one-to-one correspondence between the minimal solutions of the equations and the irredundant coverings, as previously discovered by Markovskii [On the relation between equations with max-product composition and the covering problem, Fuzzy Sets and Systems, 153 (2005) 261–273] for fuzzy relational equations with max-product composition. Since max-product composition is a special case of max-Archimedean t-norm composition, this work extends Markovskii's work to fuzzy relational equations with max-Archimedean t-norm composition. An extension of Markovskii's algorithm is implemented, yielding a processing time linearly proportional to the square of the number of minimal solutions.