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
    Event13th International Conference on Tools and Algorithms for Construction and Analysis of Systems, TACAS 2007 - Braga, Portugal
    Duration: 24 Mar 20071 Apr 2007
    Conference number: 13

    Publication series

    NameLecture notes in computer science
    PublisherSpringer
    Number2
    Volume4424

    Conference

    Conference13th International Conference on Tools and Algorithms for Construction and Analysis of Systems, TACAS 2007
    Abbreviated titleTACAS
    CountryPortugal
    CityBraga
    Period24/03/071/04/07

    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