Probabilistic weak simulation is decidable in polynomial time

Christel Baier, Holger Hermanns, Joost-Pieter Katoen

    Research output: Contribution to journalArticleAcademicpeer-review

    16 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 languageEnglish
    Pages (from-to)123-130
    JournalInformation processing letters
    Volume89
    Issue number3
    DOIs
    Publication statusPublished - 2004

    Keywords

    • FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS
    • FMT-PM: PROBABILISTIC METHODS

    Fingerprint

    Dive into the research topics of 'Probabilistic weak simulation is decidable in polynomial time'. Together they form a unique fingerprint.

    Cite this