On the Metric-Based Approximate Minimization of Markov Chains

Research output: Contribution to journalConference article in JournalResearchpeer-review

4 Citations (Scopus)

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.
Original languageEnglish
JournalLeibniz International Proceedings in Informatics
Volume80
Issue number44
Pages (from-to)1
Number of pages14
ISSN1868-8969
DOIs
Publication statusPublished - 2017
Event44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) - Warsaw, Poland
Duration: 10 Jul 201714 Jul 2017
http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=59138

Conference

Conference44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
CountryPoland
CityWarsaw
Period10/07/201714/07/2017
Internet address

Fingerprint

Markov processes
Experiments

Keywords

  • Behavioral distances
  • Probabilistic Models
  • Automata Minimization

Cite this

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

In: Leibniz International Proceedings in Informatics, Vol. 80, No. 44, 2017, p. 1.

Research output: Contribution to journalConference article in JournalResearchpeer-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 -