Flow faster: efficient decision algorithms for probabilistic simulations

Lijun Zhang, H. Hermanns, Friedrich Eisenbrand, D.N. Jansen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Citations (Scopus)

Abstract

Abstraction techniques based on simulation relations have become an important and effective proof technique to avoid the infamous state space explosion problem. In the context of Markov chains, strong and weak simulation relations have been proposed, together with corresponding decision algorithms, but it is as yet unclear whether they can be use as effectively as their non-stochastic counterparts. This paper presents drastically improved algorithms to decide whether one (discrete- or continuous-time) Markov chain strongly or weeakly simulaties another. The key innovation is the use of parametric maximum flow techniques to amortize computations.
Original languageUndefined
Title of host publicationTools and algorithms for the construction and analysis of systems
EditorsO. Grumberg, M. Huth
Place of PublicationBerlin
PublisherSpringer
Pages155-169
Number of pages15
ISBN (Print)978-3-540-71208-4
DOIs
Publication statusPublished - 2007

Publication series

NameLecture notes in computer science
PublisherSpringer
Number2
Volume4424

Keywords

  • EWI-9650
  • IR-63994
  • METIS-241574

Cite this

Zhang, L., Hermanns, H., Eisenbrand, F., & Jansen, D. N. (2007). Flow faster: efficient decision algorithms for probabilistic simulations. In O. Grumberg, & M. Huth (Eds.), Tools and algorithms for the construction and analysis of systems (pp. 155-169). [10.1007/978-3-540-71209-1_14] (Lecture notes in computer science; Vol. 4424, No. 2). Berlin: Springer. https://doi.org/10.1007/978-3-540-71209-1_14
Zhang, Lijun ; Hermanns, H. ; Eisenbrand, Friedrich ; Jansen, D.N. / Flow faster: efficient decision algorithms for probabilistic simulations. Tools and algorithms for the construction and analysis of systems. editor / O. Grumberg ; M. Huth. Berlin : Springer, 2007. pp. 155-169 (Lecture notes in computer science; 2).
@inproceedings{b0d06948012e4cdb9bf81255087116dd,
title = "Flow faster: efficient decision algorithms for probabilistic simulations",
abstract = "Abstraction techniques based on simulation relations have become an important and effective proof technique to avoid the infamous state space explosion problem. In the context of Markov chains, strong and weak simulation relations have been proposed, together with corresponding decision algorithms, but it is as yet unclear whether they can be use as effectively as their non-stochastic counterparts. This paper presents drastically improved algorithms to decide whether one (discrete- or continuous-time) Markov chain strongly or weeakly simulaties another. The key innovation is the use of parametric maximum flow techniques to amortize computations.",
keywords = "EWI-9650, IR-63994, METIS-241574",
author = "Lijun Zhang and H. Hermanns and Friedrich Eisenbrand and D.N. Jansen",
note = "10.1007/978-3-540-71209-1_14",
year = "2007",
doi = "10.1007/978-3-540-71209-1_14",
language = "Undefined",
isbn = "978-3-540-71208-4",
series = "Lecture notes in computer science",
publisher = "Springer",
number = "2",
pages = "155--169",
editor = "O. Grumberg and M. Huth",
booktitle = "Tools and algorithms for the construction and analysis of systems",

}

Zhang, L, Hermanns, H, Eisenbrand, F & Jansen, DN 2007, Flow faster: efficient decision algorithms for probabilistic simulations. in O Grumberg & M Huth (eds), Tools and algorithms for the construction and analysis of systems., 10.1007/978-3-540-71209-1_14, Lecture notes in computer science, no. 2, vol. 4424, Springer, Berlin, pp. 155-169. https://doi.org/10.1007/978-3-540-71209-1_14

Flow faster: efficient decision algorithms for probabilistic simulations. / Zhang, Lijun; Hermanns, H.; Eisenbrand, Friedrich; Jansen, D.N.

Tools and algorithms for the construction and analysis of systems. ed. / O. Grumberg; M. Huth. Berlin : Springer, 2007. p. 155-169 10.1007/978-3-540-71209-1_14 (Lecture notes in computer science; Vol. 4424, No. 2).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Flow faster: efficient decision algorithms for probabilistic simulations

AU - Zhang, Lijun

AU - Hermanns, H.

AU - Eisenbrand, Friedrich

AU - Jansen, D.N.

N1 - 10.1007/978-3-540-71209-1_14

PY - 2007

Y1 - 2007

N2 - Abstraction techniques based on simulation relations have become an important and effective proof technique to avoid the infamous state space explosion problem. In the context of Markov chains, strong and weak simulation relations have been proposed, together with corresponding decision algorithms, but it is as yet unclear whether they can be use as effectively as their non-stochastic counterparts. This paper presents drastically improved algorithms to decide whether one (discrete- or continuous-time) Markov chain strongly or weeakly simulaties another. The key innovation is the use of parametric maximum flow techniques to amortize computations.

AB - Abstraction techniques based on simulation relations have become an important and effective proof technique to avoid the infamous state space explosion problem. In the context of Markov chains, strong and weak simulation relations have been proposed, together with corresponding decision algorithms, but it is as yet unclear whether they can be use as effectively as their non-stochastic counterparts. This paper presents drastically improved algorithms to decide whether one (discrete- or continuous-time) Markov chain strongly or weeakly simulaties another. The key innovation is the use of parametric maximum flow techniques to amortize computations.

KW - EWI-9650

KW - IR-63994

KW - METIS-241574

U2 - 10.1007/978-3-540-71209-1_14

DO - 10.1007/978-3-540-71209-1_14

M3 - Conference contribution

SN - 978-3-540-71208-4

T3 - Lecture notes in computer science

SP - 155

EP - 169

BT - Tools and algorithms for the construction and analysis of systems

A2 - Grumberg, O.

A2 - Huth, M.

PB - Springer

CY - Berlin

ER -

Zhang L, Hermanns H, Eisenbrand F, Jansen DN. Flow faster: efficient decision algorithms for probabilistic simulations. In Grumberg O, Huth M, editors, Tools and algorithms for the construction and analysis of systems. Berlin: Springer. 2007. p. 155-169. 10.1007/978-3-540-71209-1_14. (Lecture notes in computer science; 2). https://doi.org/10.1007/978-3-540-71209-1_14