FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Approximate Abstractions of Markov Chains with Interval Decision Processes

Authors: Yuriy Zacchia Lun, Jack Wheatley, Alessandro D'Innocenzo and Alessandro Abate

Paper Information

Title:Approximate Abstractions of Markov Chains with Interval Decision Processes
Authors:Yuriy Zacchia Lun, Jack Wheatley, Alessandro D'Innocenzo and Alessandro Abate
Proceedings:ADHS Full papers
Editor: Alessandro Abate
Keywords:aaa, bbb, ccc
Abstract:

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.

Pages:6
Talk:Jul 11 15:15 (Session 66C: Stochastic systems 1)
Paper: