Parameter Synthesis Algorithms for Parametric Interval Markov Chains - Formal Techniques for Distributed Objects, Components, and Systems (FORTE 2018) Access content directly
Conference Papers Year : 2018

Parameter Synthesis Algorithms for Parametric Interval Markov Chains

Laure Petrucci
Jaco van De Pol
  • Function : Author
  • PersonId : 1033825

Abstract

This paper considers the consistency problem for Parametric Interval Markov Chains. In particular, we introduce a co-inductive definition of consistency, which improves and simplifies previous inductive definitions considerably. The equivalence of the inductive and co-inductive definitions has been formally proved in the interactive theorem prover PVS.These definitions lead to forward and backward algorithms, respectively, for synthesizing an expression for all parameters for which a given PIMC is consistent. We give new complexity results when tackling the consistency problem for IMCs (i.e. without parameters). We provide a sharper upper bound, based on the longest simple path in the IMC. The algorithms are also optimized, using different techniques (dynamic programming cache, polyhedra representation, etc.). They are evaluated on a prototype implementation. For parameter synthesis, we use Constraint Logic Programming and the PARMA library for convex polyhedra.
Fichier principal
Vignette du fichier
469043_1_En_7_Chapter.pdf (372.46 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01824814 , version 1 (27-06-2018)

Licence

Attribution

Identifiers

Cite

Laure Petrucci, Jaco van De Pol. Parameter Synthesis Algorithms for Parametric Interval Markov Chains. 38th International Conference on Formal Techniques for Distributed Objects, Components, and Systems (FORTE), Jun 2018, Madrid, Spain. pp.121-140, ⟨10.1007/978-3-319-92612-4_7⟩. ⟨hal-01824814⟩
72 View
64 Download

Altmetric

Share

Gmail Facebook X LinkedIn More