Bound-preserving composition for Markov reward models

David Daly, Peter Buchholz, William H. Sanders

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Stochastic orders can be applied to Markov reward models and used to aggregate models, while introducing a bounded error. Aggregation reduces the number of states in a model, mitigating the effect of the state-space explosion and enabling the wider use of Markov reward models. Existing aggregation techniques based upon stochastic orders are limited by a combination of strong requirements on the structure of the model, and complexity in determining the stochastic order and generating the aggregated model. We develop a set of general conditions in which models can be analyzed and aggregated compositionally, dramatically lowering the complexity of the aggregation and solution of the model. When these conditions are combined with a recently developed general stochastic order for Markov reward models, significantly larger models can be solved than was previously possible for a large class of models.

Original languageEnglish (US)
Title of host publicationThird International Conference on the Quantitative Evaluation of Systems, QEST 2006
Pages243-252
Number of pages10
DOIs
StatePublished - Dec 1 2006
Event3rd International Conference on the Quantitative Evaluation of Systems, QEST 2006 - Riverside, CA, United States
Duration: Sep 11 2006Sep 14 2006

Publication series

NameThird International Conference on the Quantitative Evaluation of Systems, QEST 2006

Other

Other3rd International Conference on the Quantitative Evaluation of Systems, QEST 2006
Country/TerritoryUnited States
CityRiverside, CA
Period9/11/069/14/06

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Bound-preserving composition for Markov reward models'. Together they form a unique fingerprint.

Cite this