Long-Run Rewards for Markov Automata

被引：10

作者：

Butkova, Yuliya ^{[1
]}

Wimmer, Ralf ^{[2
]}

Hermanns, Holger ^{[1
]}

机构：

[1] Saarland Univ, Saarbrucken, Germany

[2] Albert Ludwigs Univ Freiburg, Freiburg, Germany

来源：

TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, TACAS 2017, PT II | 2017年 / 10206卷

关键词：

D O I：

10.1007/978-3-662-54580-5_11

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Markov automata are a powerful formalism for modelling systems which exhibit nondeterminism, probabilistic choices and continuous stochastic timing. We consider the computation of long-run average rewards, the most classical problem in continuous-time Markov model analysis. We propose an algorithm based on value iteration. It improves the state of the art by orders of magnitude. The contribution is rooted in a fresh look on Markov automata, namely by treating them as an efficient encoding of CTMDPs with - in the worst case - exponentially more transitions.

引用

页码：188 / 203

页数：16

共 17 条

[1]

[Anonymous], 1994, Introduction to the Numerical Solutions of Markov Chains

[2]

[Anonymous], 2000, Dynamic programming and optimal control

[3]

[Anonymous], 2003, P 19 ACM S OP SYST P, DOI [10.1145/1165389.945450, DOI 10.1145/1165389.945450]

[4]

Bellman R. E., 1957, Dynamic programming. Princeton landmarks in mathematics

[5]

Bhattacharya R. N., 2009, STOCHASTIC PROCESSES

[6]

Chatterjee K, 2011, PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1318

[7] On Probabilistic Automata in Continuous Time [J].

Eisentraut, Christian ;

Hermanns, Holger ;

Zhang, Lijun .

25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010), 2010, :342-351

[8]

Guck Dennis, 2013, Quantitative Evaluation of Systems. 10th International Conference, QEST 2013. Proceedings: LNCS 8054, P55, DOI 10.1007/978-3-642-40196-1_5

[9]

Guck D., 2012, THESIS

[10] ANALYSIS OF TIMED AND LONG-RUN OBJECTIVES FOR MARKOV AUTOMATA [J].

Guck, Dennis ;

Hatefi, Hassan ;

Hermanns, Holger ;

Katoen, Joost-Pieter ;

Timmer, Mark .

LOGICAL METHODS IN COMPUTER SCIENCE, 2014, 10 (03)

← 1 2 →