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((m\log{l} + n)\log{n})$, 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((m\log{m} + n)\log{n})$ for the considered problem in that setting.
翻译:模糊结构, 如 fuzzy automata 、 fuzzy 过渡系统 { 模糊的社会网络 、 模糊描述逻辑中的模糊解释 已经广泛研究过 。 对于这些结构, 闪烁是一个自然的概念, 用来描述国家或个人之间无法分辨的特性。 有两种模糊结构的模糊结构 : 细微闪烁和 fuzzy 刺激。 虽然后者符合模糊模式, 前者也引起了注意, 因为在最小化结构中应用( crips 等值关系 { 、 加权社会网络 和 模糊解释 。 对于模糊描述的逻辑 。 对于这些结构, 可以为 fuzzy 定义的模糊图解, 我们用一种有效的算法来计算分区 。 它的复杂程度是 $O (m\ log { + n) log} { n} $, 其中考虑的是 $n, $m} 和 $l$ 来最小的等值关系 。 。 模拟可以为 模糊的图表 、 非 边框数 和 匹配的缩缩缩缩缩 。</s>