Document Open Access Logo

On the Metric-Based Approximate Minimization of Markov Chains

Authors Giovanni Bacci, Giorgio Bacci, Kim G. Larsen, Radu Mardare

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2017.104.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Behavioral distances
  • Probabilistic Models
  • Automata Minimization

Metrics

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

Abstract

We address the behavioral metric-based approximate minimization problem of Markov Chains (MCs), i.e., given a finite MC and a positive integer k, we are interested in finding a k-state MC of minimal distance to the original. By considering as metric the bisimilarity distance of Desharnais at al., we show that optimal approximations always exist; show that the problem can be solved as a bilinear program; and prove that its threshold problem is in PSPACE and NP-hard. Finally, we present an approach inspired by expectation maximization techniques that provides suboptimal solutions. Experiments suggest that our method gives a practical approach that outperforms the bilinear program implementation run on state-of-the-art bilinear solvers.

Cite As Get BibTex

Giovanni Bacci, Giorgio Bacci, Kim G. Larsen, and Radu Mardare. On the Metric-Based Approximate Minimization of Markov Chains. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 104:1-104:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.104

Author Details

Giovanni Bacci
Giorgio Bacci
Kim G. Larsen
Radu Mardare

References

  1. Eric Allender, Peter Burgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the complexity of numerical analysis. SIAM Journal on Computing, 38(5):1987-2006, 2009. URL: http://dx.doi.org/10.1137/070697926.
  2. Rajeev Alur, Costas Courcoubetis, Nicolas Halbwachs, David L. Dill, and Howard Wong-Toi. Minimization of timed transition systems. In CONCUR, volume 630 of Lecture Notes in Computer Science, pages 340-354. Springer, 1992. URL: http://dx.doi.org/10.1007/BFb0084802.
  3. Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, and Radu Mardare. Converging from Branching to Linear Metrics on Markov Chains. In ICTAC, volume 9399 of LNCS, pages 349-367. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-25150-9_21.
  4. Christel Baier. Polynomial time algorithms for testing probabilistic bisimulation and simulation. In CAV, volume 1102 of Lecture Notes in Computer Science, pages 50-61. Springer, 1996. URL: http://dx.doi.org/10.1007/3-540-61474-5_57.
  5. Christel Baier and Joost-Pieter Katoen. Principles of Model Checking. MIT Press, 2008. Google Scholar
  6. Borja Balle, Prakash Panangaden, and Doina Precup. A canonical form for weighted automata and applications to approximate minimization. In LICS, pages 701-712. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.70.
  7. Michael Benedikt, Rastislav Lenhardt, and James Worrell. LTL Model Checking of Interval Markov Chains. In TACAS, volume 7795 of Lecture Notes in Computer Science, pages 32-46. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-36742-7_3.
  8. Stefan Blom and Simona Orzan. A distributed algorithm for strong bisimulation reduction of state spaces. International Journal on Software Tools for Technology Transfer, 7(1):74-86, 2005. URL: http://dx.doi.org/10.1007/s10009-004-0159-4.
  9. John F. Canny. Some Algebraic and Geometric Computations in PSPACE. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC'88), pages 460-467. ACM, 1988. URL: http://dx.doi.org/10.1145/62212.62257.
  10. Di Chen, Franck van Breugel, and James Worrell. On the Complexity of Computing Probabilistic Bisimilarity. In FoSSaCS, volume 7213 of LNCS, pages 437-451. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-28729-9_29.
  11. Taolue Chen and Stefan Kiefer. On the Total Variation Distance of Labelled Markov Chains. In CSL-LICS`14, pages 33:1-33:10. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603099.
  12. Josee Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for Labeled Markov Systems. In CONCUR, volume 1664 of LNCS, pages 258-273. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-48320-9_19.
  13. Josee Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labelled Markov processes. Theoretical Compututer Science, 318(3):323-354, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2003.09.013.
  14. Kousha Etessami and Mihalis Yannakakis. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM, 56(1):1:1-1:66, 2009. URL: http://dx.doi.org/10.1145/1462153.1462154.
  15. Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite Markov Decision Processes. In UAI, pages 162-169. AUAI Press, 2004. Google Scholar
  16. Giuliana Franceschinis and Richard R. Muntz. Bounds for quasi-lumpable markov chains. Perform. Eval., 20(1-3):223-243, 1994. URL: http://dx.doi.org/10.1016/0166-5316(94)90015-9.
  17. John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189-196. Academic Press, 1971. URL: http://dx.doi.org/10.1016/B978-0-12-417750-5.50022-1.
  18. Chi-Chang Jou and Scott A.Smolka. Equivalences, congruences, and complete axiomatizations for probabilistic processes. In CONCUR'90 Theories of Concurrency: Unification and Extension, volume 458 of LNCS, pages 367-383, 1990. URL: http://dx.doi.org/10.1007/BFb0039071.
  19. Paris C. Kanellakis and Scott A. Smolka. CCS expressions, finite state processes, and three problems of equivalence. In Proceedings of the 2nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 228-240. ACM, 1983. URL: http://dx.doi.org/10.1145/800221.806724.
  20. Paris C. Kanellakis and Scott A. Smolka. CCS expressions, finite state processes, and three problems of equivalence. Information and Computation, 86(1):43-68, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90025-D.
  21. Michal Ko1cmcvara and Michael Stingl. PENBMI 2.0. http://www.penopt.com/penbmi.html. Accessed: 2016-08-28.
  22. Michal Ko1cmcvara and Michael Stingl. PENNON: A code for convex nonlinear and semidefinite programming. Optimization Methods and Software, 18(3):317-333, 2003. URL: http://dx.doi.org/10.1080/1055678031000098773.
  23. Kim Guldstrand Larsen and Arne Skou. Bisimulation through probabilistic testing. Information and Computation, 94(1):1-28, 1991. Google Scholar
  24. David Lee and Mihalis Yannakakis. Online minimization of transition systems (extended abstract). In Annual ACM Symposium on Theory of Computing, pages 264-274. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129738.
  25. Geoffrey J. McLachlan and Thriyambakam Krishnan. The EM Algorithm and Extensions. Wiley-Interscience, 2 edition, 2008. Google Scholar
  26. Robin Milner. A Calculus of Communicating Systems, volume 92 of Lecture Notes in Computer Science. Springer, 1980. URL: http://dx.doi.org/10.1007/3-540-10235-3.
  27. Edward F. Moore. Gedanken Experiments on Sequential Machines. In Automata Studies, pages 129-153. Princeton University, 1956. Google Scholar
  28. Franck van Breugel and James Worrell. Towards Quantitative Verification of Probabilistic Transition Systems. In ICALP, volume 2076 of LNCS, pages 421-432, 2001. Google Scholar
  29. Franck van Breugel and James Worrell. Approximating and computing behavioural distances in probabilistic transition systems. Theoretical Computer Science, 360(3):373-385, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.05.021.
  30. Mihali Yannakakis and David Lee. An efficient algorithm for minimizing real-time transition systems. Formal Methods in System Design, 11(2):113-136, 1997. URL: http://dx.doi.org/10.1023/A:1008621829508.
  31. Shipei Zhang and Scott A. Smolka. Towards efficient parallelization of equivalence checking algorithms. In FORTE, volume C-10 of IFIP Transactions, pages 121-135. North-Holland, 1992. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact