Name
Abstract | ||
|---|---|---|
It is well-known that fairness assumptions can be crucial for verifying progress, reactivity or other liveness properties for interleaving models. This also applies to Markov decision processes as an operational model for concurrent probabilistic systems and the task to establish tight lower or upper probability bounds for events that are specified by liveness properties. In this paper, we study general notions of strong and weak fairness constraints for Markov decision processes, formalized in an action- or state-based setting. We present a polynomially time-bounded algorithm for the quantitative analysis of an MDP against *** -automata specifications under fair worst- or best-case scenarios. Furthermore, we discuss the treatment of strong and weak fairness and process fairness constraints in the context of partial order reduction techniques for Markov decision processes that have been realized in the model checker LiQuor and rely on a variant of Peled's ample set method. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-04761-9_12 | ATVA |
Keywords | Field | DocType |
fairness constraints,ample set method,markov decision process,fairness assumption,quantitative analysis,weak fairness constraint,process fairness constraint,liveness property,model checker liquor,interleaving model,operational model,weak fairness,partial order reduction,polynomial time | Discrete mathematics,Mathematical optimization,Model checking,Markov model,Computer science,Partially observable Markov decision process,Automaton,Markov decision process,Theoretical computer science,Partial order reduction,Probabilistic logic,Liveness | Conference |
Volume | ISSN | Citations |
5799 | 0302-9743 | 12 |
PageRank | References | Authors |
0.61 | 30 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christel Baier | 1 | 3053 | 185.85 |
| Marcus Groesser | 2 | 44 | 2.32 |
| Frank Ciesinski | 3 | 299 | 14.52 |