Approximate Bisimulation Minimisation

Kiefer, S and Tang, Q ORCID: 0000-0002-9265-3011 (2021) Approximate Bisimulation Minimisation. .

Access the full-text of this item by clicking on the Open Access link.

Abstract

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.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	21 Apr 2023 12:48
Last Modified:	04 Dec 2023 12:29
DOI:	10.4230/LIPIcs.FSTTCS.2021.48
Open Access URL:	https://drops.dagstuhl.de/opus/volltexte/2021/1555...
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3169843