Approximate Abstractions of Markov Chains with Interval Decision Processes (Extended Version)
For researchers in probabilistic model checking, this provides a more accurate abstraction method for analyzing large Markov chains.
This paper introduces a new abstraction technique for reducing the state space of large Markov chains, achieving smaller one-step bisimulation error compared to standard abstractions of similar size, with comparable computational complexity.
This work introduces a new abstraction technique for reducing the state space of large, discrete-time labelled Markov chains. The abstraction leverages the semantics of interval Markov decision processes and the existing notion of approximate probabilistic bisimulation. Whilst standard abstractions make use of abstract points that are taken from the state space of the concrete model and which serve as representatives for sets of concrete states, in this work the abstract structure is constructed considering abstract points that are not necessarily selected from the states of the concrete model, rather they are a function of these states. The resulting model presents a smaller one-step bisimulation error, when compared to a like-sized, standard Markov chain abstraction. We outline a method to perform probabilistic model checking, and show that the computational complexity of the new method is comparable to that of standard abstractions based on approximate probabilistic bisimulations.