Probabilistic weak simulation is polynomially decidable

C Baier, H. Hermanns, Joost P. Katoen

    Research output: Contribution to journalArticleAcademicpeer-review

    15 Citations (Scopus)

    Abstract

    This paper considers a weak simulation preorder for Markov chains that allows for stuttering. Despite the second-order quantification in its definition, we present a polynomial-time algorithm to compute the weak simulation preorder of a finite Markov chain.
    Original languageUndefined
    Article number10.1016/j.ipl.2003.10.001
    Pages (from-to)123-252
    Number of pages130
    JournalInformation processing letters
    Volume89
    Issue number3
    DOIs
    Publication statusPublished - 2004

    Keywords

    • FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS
    • EWI-6404
    • FMT-PM: PROBABILISTIC METHODS
    • IR-63269

    Cite this