On the Metric-Based Approximate Minimization of Markov Chains

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

4 Citationer (Scopus)

Resumé

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.
OriginalsprogEngelsk
TidsskriftLeibniz International Proceedings in Informatics
Vol/bind80
Udgave nummer44
Sider (fra-til)1
Antal sider14
ISSN1868-8969
DOI
StatusUdgivet - 2017
Begivenhed44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) - Warsaw, Polen
Varighed: 10 jul. 201714 jul. 2017
http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=59138

Konference

Konference44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
LandPolen
ByWarsaw
Periode10/07/201714/07/2017
Internetadresse

Fingerprint

Markov processes
Experiments

Citer dette

@inproceedings{cba49bee4773421ea2bfedb58fc2f648,
title = "On the Metric-Based Approximate Minimization of Markov Chains",
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.",
keywords = "Behavioral distances, Probabilistic Models, Automata Minimization",
author = "Giovanni Bacci and Giorgio Bacci and Larsen, {Kim Guldstrand} and Radu Mardare",
year = "2017",
doi = "10.4230/LIPIcs.ICALP.2017.104",
language = "English",
volume = "80",
pages = "1",
journal = "Leibniz International Proceedings in Informatics",
issn = "1868-8969",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH",
number = "44",

}

On the Metric-Based Approximate Minimization of Markov Chains. / Bacci, Giovanni; Bacci, Giorgio; Larsen, Kim Guldstrand; Mardare, Radu.

I: Leibniz International Proceedings in Informatics, Bind 80, Nr. 44, 2017, s. 1.

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

TY - GEN

T1 - On the Metric-Based Approximate Minimization of Markov Chains

AU - Bacci, Giovanni

AU - Bacci, Giorgio

AU - Larsen, Kim Guldstrand

AU - Mardare, Radu

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Behavioral distances

KW - Probabilistic Models

KW - Automata Minimization

U2 - 10.4230/LIPIcs.ICALP.2017.104

DO - 10.4230/LIPIcs.ICALP.2017.104

M3 - Conference article in Journal

VL - 80

SP - 1

JO - Leibniz International Proceedings in Informatics

JF - Leibniz International Proceedings in Informatics

SN - 1868-8969

IS - 44

ER -