首页    期刊浏览 2024年09月15日 星期日
登录注册

文章基本信息

  • 标题:Approximating a Behavioural Pseudometric without Discount forProbabilistic Systems
  • 本地全文:下载
  • 作者:Franck van Breugel ; Babita Sharma ; James Worrell
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2008
  • 卷号:4
  • 期号:02
  • DOI:10.2168/LMCS-4(2:2)2008
  • 出版社:Technical University of Braunschweig
  • 摘要:

    Desharnais, Gupta, Jagadeesan and Panangaden introduced a family of behavioural pseudometrics for probabilistic transition systems. These pseudometrics are a quantitative analogue of probabilistic bisimilarity. Distance zero captures probabilistic bisimilarity. Each pseudometric has a discount factor, a real number in the interval (0, 1]. The smaller the discount factor, the more the future is discounted. If the discount factor is one, then the future is not discounted at all. Desharnais et al. showed that the behavioural distances can be calculated up to any desired degree of accuracy if the discount factor is smaller than one. In this paper, we show that the distances can also be approximated if the future is not discounted. A key ingredient of our algorithm is Tarski's decision procedure for the first order theory over real closed fields. By exploiting the Kantorovich-Rubinstein duality theorem we can restrict to the existential fragment for which more efficient decision procedures exist.

国家哲学社会科学文献中心版权所有