Parametric LTL on Markov Chains

This paper is concerned with the verification of finite Markov chains against parametrized LTL (pLTL) formulas. In pLTL, the until-modality is equipped with a bound that contains variables; e.g., $\Diamond_{\le x}\ φ$ asserts that $φ$ holds within $x$ time steps, where $x$ is a variable on natural numbers. The central problem studied in this paper is to determine the set of parameter valuations $V_{\prec p} (φ)$ for which the probability to satisfy pLTL-formula $φ$ in a Markov chain meets a given threshold $\prec p$, where $\prec$ is a comparison on reals and $p$ a probability. As for pLTL determining the emptiness of $V_{> 0}(φ)$ is undecidable, we consider several logic fragments. We consider parametric reachability properties, a sub-logic of pLTL restricted to next and $\Diamond_{\le x}$, parametric Büchi properties and finally, a maximal subclass of pLTL for which emptiness of $V_{> 0}(φ)$ is decidable.

No reviews yet.

No comments yet.