Edinburgh Research Explorer

Property-driven State-Space Coarsening for Continuous Time Markov Chains

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

Original languageEnglish
Title of host publication Quantitative Evaluation of Systems
Subtitle of host publication13th International Conference on Quantitative Evaluation of SysTems (QEST 2016)
PublisherSpringer International Publishing
Pages3-18
Number of pages16
ISBN (Electronic)978-3-319-43425-4
ISBN (Print)978-3-319-43424-7
DOIs
StatePublished - 3 Aug 2016

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer International Publishing
Volume9826
ISSN (Print)0302-9743

Abstract

Dynamical systems with large state-spaces are often expensive to thoroughly explore experimentally. Coarse-graining methods aim to define simpler systems which are more amenable to analysis and exploration; most current methods, however, focus on a priori state aggregation based on similarities in transition rates, which is not necessarily reflected in similar behaviours at the level of trajectories. We propose a way to coarsen the state-space of a system which optimally preserves the satisfaction of a set of logical specifications about the system's trajectories. Our approach is based on Gaussian Process emulation and Multi-Dimensional Scaling, a dimensionality reduction technique which optimally preserves distances in non-Euclidean spaces. We show how to obtain low-dimensional visualisations of the system's state-space from the perspective of properties' satisfaction, and how to define macro-states which behave coherently with respect to the specifications. Our approach is illustrated on a non-trivial running example, showing promising performance and high computational efficiency.

Download statistics

No data available

ID: 25700419