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

@article{617d2a59d73e485d99e5cd5113132912,
title = "Probabilistic weak simulation is polynomially decidable",
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 = "FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS, EWI-6404, FMT-PM: PROBABILISTIC METHODS, IR-63269",
author = "C Baier and H. Hermanns and Katoen, {Joost P.}",
year = "2004",
doi = "10.1016/j.ipl.2003.10.001",
language = "Undefined",
volume = "89",
pages = "123--252",
journal = "Information processing letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "3",

}

Probabilistic weak simulation is polynomially decidable. / Baier, C; Hermanns, H.; Katoen, Joost P.

In: Information processing letters, Vol. 89, No. 3, 10.1016/j.ipl.2003.10.001, 2004, p. 123-252.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Probabilistic weak simulation is polynomially decidable

AU - Baier, C

AU - Hermanns, H.

AU - Katoen, Joost P.

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 - FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS

KW - EWI-6404

KW - FMT-PM: PROBABILISTIC METHODS

KW - IR-63269

U2 - 10.1016/j.ipl.2003.10.001

DO - 10.1016/j.ipl.2003.10.001

M3 - Article

VL - 89

SP - 123

EP - 252

JO - Information processing letters

JF - Information processing letters

SN - 0020-0190

IS - 3

M1 - 10.1016/j.ipl.2003.10.001

ER -