论文标题
计算基于图形的结构的计算清晰的模拟和清晰的定向模拟
Computing Crisp Simulations and Crisp Directed Simulations for Fuzzy Graph-Based Structures
论文作者
论文摘要
像两者一样，模拟和定向模拟都用于分析基于图的结构，例如自动机，标记的过渡系统，链接的数据网络，kripke模型和描述逻辑中的解释。模拟表征了存在的模态公式，而有指示的模拟表征了正模态公式的类别。这些观念值得研究。例如，一个人可能有兴趣检查给定的有限自动机是否模拟另一个，或者链接数据网络中的对象是否具有另一个对象具有的所有正属性。为了处理模糊性和不确定性，使用基于模糊的结构而不是清晰的结构。在本文中，我们使用复杂性$ O（（M+n）n）$设计有效的算法，用于计算两个有限模糊标记的图形之间的最大的酥脆模拟和最大的Crisp定向模拟，其中$ n $是顶点的数量和$ m $是输入fuzzy图的非零evers的数量。我们还适应了它们，以计算两个有限模糊自动机之间最大的清晰模拟和最大的酥脆定向模拟。
Like bisimulations, simulations and directed simulations are used for analyzing graph-based structures such as automata, labeled transition systems, linked data networks, Kripke models and interpretations in description logic. Simulations characterize the class of existential modal formulas, whereas directed simulations characterize the class of positive modal formulas. These notions are worth studying. For example, one may be interested in checking whether a given finite automaton simulates another or whether an object in a linked data network has all positive properties that another object has. To deal with vagueness and uncertainty, fuzzy graph-based structures are used instead of crisp ones. In this article, we design efficient algorithms with the complexity $O((m+n)n)$ for computing the largest crisp simulation and the largest crisp directed simulation between two finite fuzzy labeled graphs, where $n$ is the number of vertices and $m$ is the number of nonzero edges of the input fuzzy graphs. We also adapt them to computing the largest crisp simulation and the largest crisp directed simulation between two finite fuzzy automata.
