Title | Approximate Abstractions of Markov Chains with Interval Decision Processes |
Publication Type | Conference Proceedings |
Year of Conference | 2018 |
Authors | Lun YZacchia, Wheatley J, D'Innocenzo A, Abate A |
Conference Name | IFAC Conference on Analysis and Design of Hybrid Systems |
Abstract | 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. |
C/O Department of Computer Science
Wolfson Building, Parks Rd, Oxford OX1 3QD
T: +44 (0) 18656 10767