Numerical and statistical approaches for model checking of stochastic processes

Abstract : We propose in this thesis several contributions related to the quantitative verification of systems. This discipline aims to evaluate functional and performance properties of a system. Such a verification requires two ingredients: a formal model to represent the system and a temporal logic to express the desired property. Then the evaluation is done with a statistical or numerical method. The spatial complexity of numerical methods which is proportional to the size of the state space of the model makes them impractical when the state space is very large. The method of stochastic comparison with censored Markov chains is one of the methods that reduces memory requirements by restricting the analysis to a subset of the states of the original Markov chain. In this thesis we provide new bounds that depend on the available information about the chain. We introduce a new quantitative temporal logic named Hybrid Automata Stochastic Logic (HASL), for the verification of discrete event stochastic processes (DESP). HASL employs Linear Hybrid Automata (LHA) to select prefixes of relevant execution paths of a DESP. LHA allows rather elaborate information to be collected on-the-fly during path selection, providing the user with a powerful mean to express sophisticated measures. In essence HASL provides a unifying verification framework where temporal reasoning is naturally blended with elaborate reward-based analysis. We have also developed COSMOS, a tool that implements statistical verification of HASL formulas over stochastic Petri nets. Flexible manufacturing systems (FMS) have often been modelized by Petri nets. However the modeler should have a good knowledge of this formalism. In order to facilitate such a modeling we propose a methodology of compositional modeling that is application oriented and does not require any knowledge of Petri nets by the modeler.
Document type :
Theses
Other. École normale supérieure de Cachan - ENS Cachan, 2012. English. <NNT : 2012DENS0025>


https://tel.archives-ouvertes.fr/tel-00751927
Contributor : ABES STAR <>
Submitted on : Wednesday, November 14, 2012 - 3:12:17 PM
Last modification on : Friday, January 10, 2014 - 1:18:31 PM

File

Djafri2012.pdf
fileSource_public_star

Identifiers

  • HAL Id : tel-00751927, version 1

Citation

Hilal Djafri. Numerical and statistical approaches for model checking of stochastic processes. Other. École normale supérieure de Cachan - ENS Cachan, 2012. English. <NNT : 2012DENS0025>. <tel-00751927>

Export

Share

Metrics

Consultation de
la notice

325

Téléchargement du document

116