文章基本信息

标题：On the Metric-Based Approximate Minimization of Markov Chains
本地全文：下载
作者：Giovanni Bacci ; Giorgio Bacci ; Kim G. Larsen 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：104:1-104:14
DOI：10.4230/LIPIcs.ICALP.2017.104
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Behavioral distances; Probabilistic Models; Automata Minimization