Approximate bisimulation minimisation
We propose polynomial-time algorithms to minimise labelled Markov chains whose transition probabilities are not known exactly, have been perturbed, or can only be obtained by sampling. Our algorithms are based on a new notion of an approximate bisimulation quotient, obtained by lumping together stat...
| Autori principali: | , |
|---|---|
| Natura: | Conference item |
| Lingua: | English |
| Pubblicazione: |
Schloss Dagstuhl
2021
|
| _version_ | 1826289623179984896 |
|---|---|
| author | Kiefer, S Tang, Q |
| author_facet | Kiefer, S Tang, Q |
| author_sort | Kiefer, S |
| collection | OXFORD |
| description | We propose polynomial-time algorithms to minimise labelled Markov chains whose transition probabilities are not known exactly, have been perturbed, or can only be obtained by sampling. Our algorithms are based on a new notion of an approximate bisimulation quotient, obtained by lumping together states that are exactly bisimilar in a slightly perturbed system. We present experiments that show that our algorithms are able to recover the structure of the bisimulation quotient of the unperturbed system. |
| first_indexed | 2024-03-07T02:31:42Z |
| format | Conference item |
| id | oxford-uuid:a7747534-c6fd-4c3d-b7d5-96e97317a31c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T02:31:42Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:a7747534-c6fd-4c3d-b7d5-96e97317a31c2022-03-27T02:54:46ZApproximate bisimulation minimisationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a7747534-c6fd-4c3d-b7d5-96e97317a31cEnglishSymplectic ElementsSchloss Dagstuhl2021Kiefer, STang, QWe propose polynomial-time algorithms to minimise labelled Markov chains whose transition probabilities are not known exactly, have been perturbed, or can only be obtained by sampling. Our algorithms are based on a new notion of an approximate bisimulation quotient, obtained by lumping together states that are exactly bisimilar in a slightly perturbed system. We present experiments that show that our algorithms are able to recover the structure of the bisimulation quotient of the unperturbed system. |
| spellingShingle | Kiefer, S Tang, Q Approximate bisimulation minimisation |
| title | Approximate bisimulation minimisation |
| title_full | Approximate bisimulation minimisation |
| title_fullStr | Approximate bisimulation minimisation |
| title_full_unstemmed | Approximate bisimulation minimisation |
| title_short | Approximate bisimulation minimisation |
| title_sort | approximate bisimulation minimisation |
| work_keys_str_mv | AT kiefers approximatebisimulationminimisation AT tangq approximatebisimulationminimisation |