Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Flow faster: efficient decision algorithms for probabilistic simulations
 
conference paper

Flow faster: efficient decision algorithms for probabilistic simulations

Zhang, Lijun
•
Hermanns, H.
•
Eisenbrand, Friedrich  
Show more
2007
Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2007
Tools and Algorithms for the Construction and Analysis of Systems. 13th International Conference, TACAS 2007. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007

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 ((B. Jonsson and K.G. Larsen, 1991), (C. Baier et al., 2002)), together with corresponding decision algorithms ((C. Baier et al., 2000), (C. Baier et al., 2004), but it is as yet unclear whether they can be used 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 weakly simulates another. The key innovation is the use of parametric maximum flow techniques to amortize computations

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-540-71209-1_14
Web of Science ID

WOS:000268642100006

Author(s)
Zhang, Lijun
Hermanns, H.
Eisenbrand, Friedrich  
Jansen, D. N.
Date Issued

2007

Published in
Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2007
Start page

155

End page

169

Written at

OTHER

EPFL units
DISOPT  
Event nameEvent placeEvent date
Tools and Algorithms for the Construction and Analysis of Systems. 13th International Conference, TACAS 2007. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007

Braga, Portugal

March 24 - April 1, 2007

Available on Infoscience
May 13, 2008
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/23728
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés