Document Open Access Logo

Approximate Bisimulation Minimisation

Authors Stefan Kiefer , Qiyi Tang

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.48.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Stefan Kiefer
  • Department of Computer Science, University of Oxford, UK
Qiyi Tang
  • Department of Computer Science, University of Oxford, UK

Funding

  • Kiefer, Stefan: Supported by a Royal Society University Fellowship.

Acknowledgements

We thank the anonymous reviewers of this paper for their constructive feedback.

Cite AsGet BibTex

Stefan Kiefer and Qiyi Tang. Approximate Bisimulation Minimisation. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.48

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Program verification
  • Theory of computation → Models of computation
  • Mathematics of computing → Probability and statistics
Keywords
  • Markov chains
  • Behavioural metrics
  • Bisimulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Giovanni Bacci, Giorgio Bacci, Kim G. Larsen, and Radu Mardare. On the metric-based approximate minimization of Markov chains. J. Log. Algebraic Methods Program., 100:36-56, 2018. URL: https://doi.org/10.1016/j.jlamp.2018.05.006.
  2. Hugo Bazille, Blaise Genest, Cyrille Jégourel, and Jun Sun. Global PAC bounds for learning discrete time Markov chains. In Shuvendu K. Lahiri and Chao Wang, editors, Computer Aided Verification - 32nd International Conference, CAV 2020, Los Angeles, CA, USA, July 21-24, 2020, Proceedings, Part II, volume 12225 of Lecture Notes in Computer Science, pages 304-326. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-53291-8_17.
  3. Gaoang Bian and Alessandro Abate. On the relationship between bisimulation and trace equivalence in an approximate probabilistic context. In Javier Esparza and Andrzej S. Murawski, editors, Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, volume 10203 of Lecture Notes in Computer Science, pages 321-337, 2017. URL: https://doi.org/10.1007/978-3-662-54458-7_19.
  4. Patrick Billingsley. Probability and measure. Wiley Series in Probability and Statistics. Wiley, New York, NY, USA, 3rd edition, 1995. Google Scholar
  5. Di Chen, Franck van Breugel, and James Worrell. On the complexity of computing probabilistic bisimilarity. In Lars Birkedal, editor, Foundations of Software Science and Computational Structures - 15th International Conference, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 - April 1, 2012. Proceedings, volume 7213 of Lecture Notes in Computer Science, pages 437-451. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-28729-9_29.
  6. Jianhua Chen. Properties of a new adaptive sampling method with applications to scalable learning. Web Intelligence, 13(4):215-227, 2015. URL: https://doi.org/10.3233/WEB-150322.
  7. P. D'Argenio, B. Jeannet, H. Jensen, and K. Larsen. Reachability analysis of probabilistic systems by successive refinements. In L. de Alfaro and S. Gilmore, editors, Proc. 1st Joint International Workshop on Process Algebra and Probabilistic Methods, Performance Modelling and Verification (PAPM/PROBMIV'01), volume 2165 of LNCS, pages 39-56. Springer, 2001. Google Scholar
  8. Josée Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labeled Markov systems. In Jos Baeten and Sjouke Mauw, editors, Proceedings of the 10th International Conference on Concurrency Theory, volume 1664 of Lecture Notes in Computer Science, pages 258-273, Eindhoven, The Netherlands, August 1999. Springer-Verlag. Google Scholar
  9. Josée Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labelled Markov processes. Theor. Comput. Sci., 318(3):323-354, 2004. URL: https://doi.org/10.1016/j.tcs.2003.09.013.
  10. Josée Desharnais, François Laviolette, and Mathieu Tracol. Approximate analysis of probabilistic processes: Logic, simulation and games. In Fifth International Conference on the Quantitative Evaluaiton of Systems (QEST 2008), 14-17 September 2008, Saint-Malo, France, pages 264-273. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/QEST.2008.42.
  11. S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Communications of the ACM, 28(6):637-647, 1985. Google Scholar
  12. Christian Hensel, Sebastian Junges, Joost-Pieter Katoen, Tim Quatmann, and Matthias Volk. The probabilistic model checker Storm. CoRR, abs/2002.07080, 2020. URL: http://arxiv.org/abs/2002.07080.
  13. T. Herman. Probabilistic self-stabilization. Information Processing Letters, 35(2):63-67, 1990. Google Scholar
  14. Aron Itai and Michael Rodeh. Symmetry breaking in distributed networks. Information and Computation, 88(1):60-87, September 1990. Google Scholar
  15. Stefan Kiefer and Qiyi Tang. Approximate bisimulation minimisation, 2021. URL: http://arxiv.org/abs/2110.00326.
  16. Marta Kwiatkowska, Gethin Norman, and David Parker. Prism 4.0: Verification of probabilistic real-time systems. In Ganesh Gopalakrishnan and Shaz Qadeer, editors, Proceedings of the 23rd International Conference on Computer Aided Verification, volume 6806 of Lecture Notes in Computer Science, pages 585-591, Snowbird, UT, USA, July 2011. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-22110-1_47.
  17. M. Reiter and A. Rubin. Crowds: Anonymity for web transactions. ACM Transactions on Information and System Security (TISSEC, 1(1):66-92, 1998. Google Scholar
  18. Qiyi Tang and Franck van Breugel. Deciding probabilistic bisimilarity distance one for labelled markov chains. In Hana Chockler and Georg Weissenbacher, editors, Computer Aided Verification - 30th International Conference, CAV 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings, Part I, volume 10981 of Lecture Notes in Computer Science, pages 681-699. Springer, 2018. Google Scholar
  19. Mathieu Tracol, Josée Desharnais, and Abir Zhioua. Computing distances between probabilistic automata. In Mieke Massink and Gethin Norman, editors, Proceedings Ninth Workshop on Quantitative Aspects of Programming Languages, QAPL 2011, Saarbrücken, Germany, April 1-3, 2011, volume 57 of EPTCS, pages 148-162, 2011. URL: https://doi.org/10.4204/EPTCS.57.11.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact