Computing crisp bisimulations for fuzzy structures

DOI10.1016/J.IJAR.2024.109121OpenAlexW3095251390WikidataQ130026318 ScholiaQ130026318MaRDI QIDQ6131936FDOQ6131936

Authors Linh Anh Nguyen, Dat Xuan Tran

Publication date 18 April 2024

Published in International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.15671

zbMATH Keywords

bisimulationfuzzy automatafuzzy description logicsfuzzy transition systemsweighted social networks

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37)

Abstract: Fuzzy structures such as fuzzy automata, fuzzy transition systems, weighted social networks and fuzzy interpretations in fuzzy description logics have been widely studied. For such structures, bisimulation is a natural notion for characterizing indiscernibility between states or individuals. There are two kinds of bisimulations for fuzzy structures: crisp bisimulations and fuzzy bisimulations. While the latter fits to the fuzzy paradigm, the former has also attracted attention due to the application of crisp equivalence relations, for example, in minimizing structures. Bisimulations can be formulated for fuzzy labeled graphs and then adapted to other fuzzy structures. In this article, we present an efficient algorithm for computing the partition corresponding to the largest crisp bisimulation of a given finite fuzzy labeled graph. Its complexity is of order $O((mlogl+n)logn)$, where $n$, $m$ and $l$ are the number of vertices, the number of nonzero edges and the number of different fuzzy degrees of edges of the input graph, respectively. We also study a similar problem for the setting with counting successors, which corresponds to the case with qualified number restrictions in description logics and graded modalities in modal logics. In particular, we provide an efficient algorithm with the complexity $O((mlogm+n)logn)$ for the considered problem in that setting.

Recommendations

• Computing bisimulation-based comparisons
• An efficient algorithm for computing bisimulation equivalence
• Computation of the greatest simulations and bisimulations between fuzzy automata
• Characterization and computation of approximate bisimulations for fuzzy automata
• scientific article; zbMATH DE number 1796125

Cited in

(1)

• Computing \(k\)-bisimulations for large graphs: a comparison and efficiency analysis

This page was built for publication: Computing crisp bisimulations for fuzzy structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131936)