Franck van Breugel ; Babita Sharma ; James Worrell - Approximating a Behavioural Pseudometric without Discount for<br> Probabilistic Systems

lmcs:822 - Logical Methods in Computer Science, April 9, 2008, Volume 4, Issue 2 - https://doi.org/10.2168/LMCS-4(2:2)2008
Approximating a Behavioural Pseudometric without Discount for<br> Probabilistic Systems

Authors: Franck van Breugel ; Babita Sharma ; James Worrell

    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.


    Volume: Volume 4, Issue 2
    Published on: April 9, 2008
    Accepted on: June 25, 2015
    Submitted on: September 20, 2007
    Keywords: Computer Science - Logic in Computer Science,F.3.1,F.3.2

    Linked data

    Source : ScholeXplorer IsReferencedBy DOI 10.1007/978-3-642-36742-7_1
    • 10.1007/978-3-642-36742-7_1
    • 10.1007/978-3-642-36742-7_1
    On-the-Fly exact computation of bisimilarity distances
    Bacci, Giorgio ; Bacci, Giovanni ; Larsen, Kim G. ; Mardare, Radu ;

    14 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 368 times.
    This article's PDF has been downloaded 422 times.