Approximating and computing behavioural distances in probabilistic transition systems

Journal article

In an earlier paper we presented a pseudometric on the states of a probabilistic transition system, yielding a quantitative notion of behavioural equivalence. The behavioural pseudometric was defined via the terminal coalgebra of a functor based on a metric on Borel probability measures. In the present paper we give a polynomial-time algorithm, based on linear programming, to calculate the distances between states up to a prescribed degree of accuracy. © 2006 Elsevier B.V. All rights reserved.

Authors: van Breugel, F; Worrell, J

• Publication status: Published
• Journal: THEORETICAL COMPUTER SCIENCE
• Volume: 360
• Issue: 1-3
• Pages: 373-385
• Publication date: 2006-08-21
• DOI: 10.1016/j.tcs.2006.05.021
• ISSN: 0304-3975
• Language: English
• Keywords: probabilistic transition system; linear programming; behavioural pseudometric; coalgebra; approximation