Polynomial algorithm of verification for subset of PLTL logic

P. V. Lebedev

Tver State University

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: Markov chains, PLTL, temporal logics, verification of dynamic properties.

UDC: 517.51+514.17

Received: 27.12.2012