Polynomial Algorithm of Verication for Subset of PLTL Logic

Abstract

In this article a polynomial algorithm is described of verification of dynamic properties of Markov chains described by formulas of a subset of temporal logic PLTL (propositional temporal logic of linear time). The algorithm allows to find probability of the validity of the formula on the Markov chain, and also set of trajectories on which the verified formula is true.

Keywords

• цепи Маркова
• проверка на моделях
• темпоральные логики
• PLTL
• верификация динамических свойств