000121645 001__ 121645
000121645 005__ 20190812205145.0
000121645 02470 $$2ISI$$a000268642100006
000121645 037__ $$aCONF
000121645 245__ $$aFlow faster: efficient decision algorithms for probabilistic simulations
000121645 260__ $$c2007
000121645 269__ $$a2007
000121645 336__ $$aConference Papers
000121645 520__ $$aAbstraction 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
000121645 700__ $$aZhang, Lijun
000121645 700__ $$aHermanns, H.
000121645 700__ $$0240331$$g183121$$aEisenbrand, Friedrich
000121645 700__ $$aJansen, D. N.
000121645 7112_ $$cBraga, Portugal
000121645 773__ $$tTools 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. Proceedings (Lecture Notes in Computer Science Vol. 4424)$$q155-69
000121645 909C0 $$xU11879$$pDISOPT$$0252111
000121645 909CO $$pconf$$pSB$$ooai:infoscience.tind.io:121645
000121645 937__ $$aDISOPT-CONF-2007-004
000121645 970__ $$a9366031/DISOPT
000121645 973__ $$sPUBLISHED$$aOTHER
000121645 980__ $$aCONF