Reflection symmetry detection to reduce the state space of Markovian models

摘要

A model-based evaluation of a system's design often considers to what degree components need to be available multiple times in order to reach a desired level of availability, reliability or dependability. Multiple components of the same kind then lead to models with regular structures. In stochastic models, especially Markovian models, such regularities have been studied for a long time and are used to establish lumpability results that help to achieve a significant state space reduction and alleviate the effects of the infamous state space explosion problem. In this paper, we introduce a new procedure to identify and reduce Markovian models that are built in a compositional manner based on sharing state variables. This procedure can also detect symmetries based on reflection in spatial models where state variables can commute. The results extend existing work of Obal, McQuinn, and Sanders and will contribute to Mobius, a multi-paradigm, multi-solution framework for the model-based dependability and performance assessment of systems.