RT journal article
T1 Minimal solutions of fuzzy relation equations via maximal independent elements
A1 Lobo Palacios, David
A1 Medina Moreno, Jesús
A1 Merkl, Timo Camillo
A1 Pichler, Reinhard
A2 Matemáticas
K1 Enumeration
K1 Fuzzy relation equations
K1 Independent sets
K1 Minimal solutions
AB 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.
PB Elsevier Inc.
SN 0020-0255
YR 2025
FD 2025
LK http://hdl.handle.net/10498/36033
UL http://hdl.handle.net/10498/36033
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 10-may-2026