Approximating and computing behavioural distances in probabilistic transition systems
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 pres...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2006
|
| _version_ | 1826267818499244032 |
|---|---|
| author | van Breugel, F Worrell, J |
| author_facet | van Breugel, F Worrell, J |
| author_sort | van Breugel, F |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T21:00:03Z |
| format | Journal article |
| id | oxford-uuid:3a9526c8-9a31-4da7-a919-4c836e0b9c7c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:00:03Z |
| publishDate | 2006 |
| record_format | dspace |
| spelling | oxford-uuid:3a9526c8-9a31-4da7-a919-4c836e0b9c7c2022-03-26T14:02:26ZApproximating and computing behavioural distances in probabilistic transition systemsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3a9526c8-9a31-4da7-a919-4c836e0b9c7cEnglishSymplectic Elements at Oxford2006van Breugel, FWorrell, JIn 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. |
| spellingShingle | van Breugel, F Worrell, J Approximating and computing behavioural distances in probabilistic transition systems |
| title | Approximating and computing behavioural distances in probabilistic transition systems |
| title_full | Approximating and computing behavioural distances in probabilistic transition systems |
| title_fullStr | Approximating and computing behavioural distances in probabilistic transition systems |
| title_full_unstemmed | Approximating and computing behavioural distances in probabilistic transition systems |
| title_short | Approximating and computing behavioural distances in probabilistic transition systems |
| title_sort | approximating and computing behavioural distances in probabilistic transition systems |
| work_keys_str_mv | AT vanbreugelf approximatingandcomputingbehaviouraldistancesinprobabilistictransitionsystems AT worrellj approximatingandcomputingbehaviouraldistancesinprobabilistictransitionsystems |