Probabilistic weak simulation is decidable in polynomial time

Christel Baier; Holger Hermanns; Joost-Pieter Katoen

doi:10.1016/j.ipl.2003.10.001

Probabilistic weak simulation is decidable in polynomial time

Christel Baier
, Holger Hermanns
, Joost-Pieter Katoen

Research output: Contribution to journal › Article › Academic › peer-review

16 Citations (Scopus)

20 Downloads (Pure)

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 language	English
Pages (from-to)	123-130
Journal	Information processing letters
Volume	89
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2003.10.001
Publication status	Published - 2004

Keywords

2020 OA procedure
FMT-PM: PROBABILISTIC METHODS
FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS

Access to Document

10.1016/j.ipl.2003.10.001

Baier2004probabilisticFinal published version, 232 KBLicence: Taverne

Cite this

@article{617d2a59d73e485d99e5cd5113132912,

title = "Probabilistic weak simulation is decidable in polynomial time",

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.",

keywords = "2020 OA procedure, FMT-PM: PROBABILISTIC METHODS, FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS",

author = "Christel Baier and Holger Hermanns and Joost-Pieter Katoen",

year = "2004",

doi = "10.1016/j.ipl.2003.10.001",

language = "English",

volume = "89",

pages = "123--130",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Probabilistic weak simulation is decidable in polynomial time

AU - Baier, Christel

AU - Hermanns, Holger

AU - Katoen, Joost-Pieter

PY - 2004

Y1 - 2004

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

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

KW - 2020 OA procedure

KW - FMT-PM: PROBABILISTIC METHODS

KW - FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS

U2 - 10.1016/j.ipl.2003.10.001

DO - 10.1016/j.ipl.2003.10.001

M3 - Article

SN - 0020-0190

VL - 89

SP - 123

EP - 130

JO - Information processing letters

JF - Information processing letters

IS - 3

ER -

Probabilistic weak simulation is decidable in polynomial time

Abstract

Keywords

Access to Document

Fingerprint

Cite this