Computing the fuzzy partition corresponding to the greatest fuzzy auto-bisimulation of a fuzzy graph-based structure under the Gödel semantics.

The similarity measure based on fuzzy bisimulation has the Hennessy-Milner property as a strong logical foundation. It is useful for classification and clustering. In this work, we design an efficient algorithm with the complexity O ((m log ⁡ l + n) log ⁡ n) for computing the fuzzy partition corresponding to the greatest fuzzy auto-bisimulation of a finite fuzzy labeled graph G under the Gödel semantics, where n , m and l are the number of vertices, the number of non-zero edges and the number of different fuzzy degrees of edges of G , respectively. Our notion of fuzzy partition is novel, defined for finite sets with respect to the Gödel t-norm, with the aim to facilitate the computation of the greatest fuzzy auto-bisimulation. By using that algorithm, we also provide an algorithm with the complexity O (m ⋅ log ⁡ l ⋅ log ⁡ n + n 2) for computing the greatest fuzzy bisimulation between two finite fuzzy labeled graphs under the Gödel semantics. This latter algorithm is better (has a lower complexity order) than the previously known algorithms for the considered problem. Our algorithms can be restated for other fuzzy graph-based structures such as fuzzy automata, fuzzy labeled transition systems, fuzzy Kripke models, fuzzy social networks and fuzzy interpretations in fuzzy description logics. [ABSTRACT FROM AUTHOR]