×

zbMATH — the first resource for mathematics

On the metric-based approximate minimization of Markov chains. (English) Zbl 1400.68098
Summary: In this paper we address the approximate minimization problem of Markov Chains (MCs) from a behavioral metric-based perspective. Specifically, given a finite MC and a positive integer \(k\), we are looking for an MC with at most \(k\) states having minimal distance to the original. The metric considered in this work is the bisimilarity distance of Desharnais et al. For this metric we show that (1) optimal approximations always exist; (2) the problem has a bilinear program characterization; and (3) prove that its threshold problem is in PSPACE and NP-hard.
In addition to the bilinear program solution, we present an approach inspired by expectation maximization techniques for computing suboptimal solutions to the problem. Experiments suggest that our method gives a practical approach that outperforms the bilinear program implementation run on state-of-the-art bilinear solvers.

MSC:
68Q45 Formal languages and automata
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Software:
PENNON
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bacci, G.; Bacci, G.; Larsen, K. G.; Mardare, R., On the metric-based approximate minimization of Markov chains, (Chatzigiannakis, I.; Indyk, P.; Kuhn, F.; Muscholl, A., 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), LIPIcs. Leibniz Int. Proc. Inform., vol. 80, (2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 104:1-104:14 · Zbl 1400.68098
[2] Moore, E. F., Gedanken experiments on sequential machines, (Automata Studies, (1956), Princeton University), 129-153
[3] Hopcroft, J., An \(n \log n\) algorithm for minimizing states in a finite automaton, (Kohavi, Z.; Paz, A., Theory of Machines and Computations, (1971), Academic Press), 189-196
[4] Kanellakis, P. C.; Smolka, S. A., CCS expressions, finite state processes, and three problems of equivalence, (Proceedings of the 2nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, (1983), ACM), 228-240
[5] Kanellakis, P. C.; Smolka, S. A., CCS expressions, finite state processes, and three problems of equivalence, Inf. Comput., 86, 1, 43-68, (1990) · Zbl 0705.68063
[6] Milner, R., A calculus of communicating systems, Lect. Notes Comput. Sci., vol. 92, (1980), Springer · Zbl 0452.68027
[7] Baier, C., Polynomial time algorithms for testing probabilistic bisimulation and simulation, (CAV, Lect. Notes Comput. Sci., vol. 1102, (1996), Springer), 50-61
[8] Larsen, K. G.; Skou, A., Bisimulation through probabilistic testing, Inf. Comput., 94, 1, 1-28, (1991) · Zbl 0756.68035
[9] Alur, R.; Courcoubetis, C.; Halbwachs, N.; Dill, D. L.; Wong-Toi, H., Minimization of timed transition systems, (CONCUR, Lect. Notes Comput. Sci., vol. 630, (1992), Springer), 340-354
[10] Yannakakis, M.; Lee, D., An efficient algorithm for minimizing real-time transition systems, Form. Methods Syst. Des., 11, 2, 113-136, (1997)
[11] Zhang, S.; Smolka, S. A., Towards efficient parallelization of equivalence checking algorithms, (FORTE, IFIP Trans., vol. C-10, (1992), North-Holland), 121-135
[12] Blom, S.; Orzan, S., A distributed algorithm for strong bisimulation reduction of state spaces, Int. J. Softw. Tools Technol. Transf., 7, 1, 74-86, (2005)
[13] Lee, D.; Yannakakis, M., Online minimization of transition systems (extended abstract), (Annual ACM Symposium on Theory of Computing, (1992), ACM), 264-274
[14] Jou, C.-C.; Smolka, S. A., Equivalences, congruences, and complete axiomatizations for probabilistic processes, (CONCUR’90 Theories of Concurrency: Unification and Extension, Lect. Notes Comput. Sci., vol. 458, (1990)), 367-383
[15] Desharnais, J.; Gupta, V.; Jagadeesan, R.; Panangaden, P., Metrics for labeled Markov systems, (CONCUR, Lect. Notes Comput. Sci., vol. 1664, (1999), Springer), 258-273 · Zbl 0939.68081
[16] van Breugel, F.; Worrell, J., Towards quantitative verification of probabilistic transition systems, (ICALP, Lect. Notes Comput. Sci., vol. 2076, (2001)), 421-432 · Zbl 0986.68093
[17] van Breugel, F.; Worrell, J., Approximating and computing behavioural distances in probabilistic transition systems, Theor. Comput. Sci., 360, 3, 373-385, (2006) · Zbl 1097.68102
[18] Chen, D.; van Breugel, F.; Worrell, J., On the complexity of computing probabilistic bisimilarity, (FoSSaCS, Lect. Notes Comput. Sci., vol. 7213, (2012), Springer), 437-451 · Zbl 1352.68096
[19] Ferns, N.; Panangaden, P.; Precup, D., Metrics for finite Markov decision processes, (UAI, (2004), AUAI Press), 162-169
[20] Kočvara, M.; Stingl, M., PENNON: a code for convex nonlinear and semidefinite programming, Optim. Methods Softw., 18, 3, 317-333, (2003) · Zbl 1037.90003
[21] Kočvara, M.; Stingl, M., Penbmi 2.0, (2016)
[22] McLachlan, G. J.; Krishnan, T., The EM algorithm and extensions, (2008), Wiley-Interscience · Zbl 1165.62019
[23] Benedikt, M.; Lenhardt, R.; Worrell, J., LTL model checking of interval Markov chains, (TACAS, Lect. Notes Comput. Sci., vol. 7795, (2013), Springer), 32-46 · Zbl 1381.68147
[24] Franceschinis, G.; Muntz, R. R., Bounds for quasi-lumpable Markov chains, Perform. Eval., 20, 1-3, 223-243, (1994)
[25] Balle, B.; Panangaden, P.; Precup, D., A canonical form for weighted automata and applications to approximate minimization, (LICS, (2015), IEEE Computer Society), 701-712 · Zbl 1401.68145
[26] Desharnais, J.; Gupta, V.; Jagadeesan, R.; Panangaden, P., Metrics for labelled Markov processes, Theor. Comput. Sci., 318, 3, 323-354, (2004) · Zbl 1068.68093
[27] Baier, C.; Katoen, J.-P., Principles of model checking, (2008), MIT Press
[28] Canny, J. F., Some algebraic and geometric computations in PSPACE, (Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC’88), (1988), ACM), 460-467
[29] Derisavi, S.; Hermanns, H.; Sanders, W. H., Optimal state-space lumping in Markov chains, Inf. Process. Lett., 87, 6, 309-315, (2003) · Zbl 1189.68039
[30] Bacci, G.; Bacci, G.; Larsen, K. G.; Mardare, R., Converging from branching to linear metrics on Markov chains, (ICTAC, Lect. Notes Comput. Sci., vol. 9399, (2015), Springer), 349-367 · Zbl 1407.68277
[31] Bacci, G.; Bacci, G.; Larsen, K. G.; Mardare, R., On-the-fly exact computation of bisimilarity distances, (TACAS, Lect. Notes Comput. Sci., vol. 7795, (2013)), 1-15 · Zbl 1381.68218
[32] Tang, Q.; van Breugel, F., Algorithms to compute probabilistic bisimilarity distances for labelled Markov chains, (Meyer, R.; Nestmann, U., 28th International Conference on Concurrency Theory (CONCUR 2017), LIPIcs. Leibniz Int. Proc. Inform., vol. 85, (2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 27:1-27:16
[33] Chen, T.; Kiefer, S., On the total variation distance of labelled Markov chains, (CSL-LICS’14, (2014), ACM), 33:1-33:10 · Zbl 1395.68202
[34] Etessami, K.; Yannakakis, M., Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations, J. ACM, 56, 1, 1:1-1:66, (2009) · Zbl 1325.68091
[35] Allender, E.; Bürgisser, P.; Kjeldgaard-Pedersen, J.; Miltersen, P. B., On the complexity of numerical analysis, SIAM J. Comput., 38, 5, 1987-2006, (2009) · Zbl 1191.68329
[36] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and real computation, (1998), Springer-Verlag New York, Inc., Secaucus, NJ, USA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.