Minimal solutions of fuzzy relation equations via maximal independent elements

Abstract

Fuzzy relation equations (FRE) are a useful formalism with a broad number of applications in different computer science areas. Testing if a solution exists and, if so, computing the unique greatest solution is straightforward. In contrast, the computation of minimal solutions is more complex. In particular, even in FRE with a very simple structure, the number of minimal solutions can increase exponentially. However, minimal solutions are immensely useful since, under mild conditions, they (together with the greatest solution) allow one to describe the entire space of solutions to an FRE. The main result of this work is a new method for enumerating the set of minimal solutions. It works by establishing a relationship between coverings of FRE and maximal independent elements of (hyper-)boxes. We can thus make efficient enumeration methods for maximal independent elements of (hyper-)boxes applicable also to our setting of FRE, where the operator considered in the composition of fuzzy relations only needs to preserve suprema of arbitrary subsets and infima of non-empty subsets. More specifically, we thus show that the enumeration of the minimal solutions of an FRE can be done with incremental quasi-polynomial delay.