Higher-Order Approximations for Verification of Stochastic Hybrid Systems

Sadegh Esmaeil Zadeh Soudjani, Alessandro Abate

Abstract

This work investigates the approximate verification of probabilistic specifications expressed as any non-nested PCTL formula over Markov processes on general state spaces. The contribution puts forward new algorithms, based on higher-order function approximation, for the efficient computation of approximate solutions with explicit bounds on the error. Approximation error related to higher-order approximations can be substantially lower than those for piece-wise constant (zeroth-order) approximations known in the literature and, unlike the latter, can display convergence in time to a finite value. Furthermore, higher-order approximation procedures, which depend on the partitioning of the state space, can lead to lower partition cardinality than the related piece-wise constant ones. The work is first presented for Markov processes over Euclidean spaces and thereafter extended to hybrid spaces characterizing models known as Stochastic Hybrid Systems.
BibTeX
@inproceedings{soudjani2012higher,
  author = {Sadegh Esmaeil Zadeh Soudjani and Alessandro Abate},
  title = {{Higher-Order Approximations for Verification of Stochastic Hybrid Systems}},
  booktitle = {ATVA},
  year = {2012},
  doi = {10.1007/978-3-642-33386-6\_32},
}

Loading related content...

Figure