Polynomial-time algorithms for computing distances of fuzzy transition systems
Polynomial-time algorithms for computing distances of fuzzy transition systems
复制标题
用于计算模糊转移系统距离的多项式时间算法
DOI：
10.1016/j.tcs.2018.03.002
复制
发表时间：
2017-01
影响因子：
1.1
通讯作者：
Cao Yongzhi
中科院分区：
文献类型：
--
作者：
Chen Taolue;Han Tingting;Cao Yongzhi
最近文献中提出了行为距离来度量（非确定性）模糊过渡系统中两个状态的相似性。这样的距离，定义为一个伪超度量的状态空间的模型，提供了一个定量模拟的双相似性。在本文中，我们专注于计算这些距离的问题。我们首先通过引入折扣来扩展伪超度量的定义，使得折扣因子等于1捕获了原始定义。然后，我们提供多项式时间算法来计算的行为距离，在非折扣和折扣设置。在前一种情况下，算法是强多项式的。
Behaviour distances to measure the resemblance of two states in a (nondeterministic) fuzzy transition system have been proposed recently in literature. Such a distance, defined as a pseudo-ultrametric over the state space of the model, provides a quantitative analogue of bisimilarity. In this paper, we focus on the problem of computing these distances. We first extend the definition of the pseudo-ultrametric by introducing discount such that the discounting factor being equal to 1 captures the original definition. We then provide polynomial-time algorithms to calculate the behavioural distances, in both the non-discounted and the discounted setting. The algorithm is strongly polynomial in the former case.
登录
查看更多内容
DOI：
--
发表时间：
--
期刊：
--
影响因子：
--
作者：
Taolue Chen;Tingting Han;Jian Lu
通讯作者：
Taolue Chen;Tingting Han;Jian Lu
DOI：
--
发表时间：
2008-04
期刊：
--
影响因子：
--
作者：
C. Baier;J. Katoen
通讯作者：
C. Baier;J. Katoen
DOI：
10.1007/3-540-44685-0_23
发表时间：
2001-08
期刊：
--
影响因子：
--
作者：
F. Breugel;J. Worrell
通讯作者：
F. Breugel;J. Worrell
DOI：
10.1016/j.tcs.2004.09.035
发表时间：
2005-02
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
F. Breugel;J. Worrell
通讯作者：
F. Breugel;J. Worrell
DOI：
10.1016/j.ijar.2014.10.001
发表时间：
2015
期刊：
Int. J. Approx. Reason.
影响因子：
--
作者：
Haiyu Pan;Yongming Li;Yongzhi Cao
通讯作者：
Haiyu Pan;Yongming Li;Yongzhi Cao