Geodesic
Polynomial algorithm of verification for subset of PLTL logic
Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 2, pp. 115-137.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : Markov chains
Keywords: PLTL, temporal logics, verification of dynamic properties. 
@article{MAIS_2012_19_2_a8,
     author = {P. V. Lebedev},
     title = {Polynomial algorithm of verification for subset of {PLTL} logic},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {115--137},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2012_19_2_a8/}
}
TY  - JOUR
AU  - P. V. Lebedev
TI  - Polynomial algorithm of verification for subset of PLTL logic
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2012
SP  - 115
EP  - 137
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2012_19_2_a8/
LA  - ru
ID  - MAIS_2012_19_2_a8
ER  - 
%0 Journal Article
%A P. V. Lebedev
%T Polynomial algorithm of verification for subset of PLTL logic
%J Modelirovanie i analiz informacionnyh sistem
%D 2012
%P 115-137
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2012_19_2_a8/
%G ru
%F MAIS_2012_19_2_a8
P. V. Lebedev. Polynomial algorithm of verification for subset of PLTL logic. Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 2, pp. 115-137. http://geodesic.mathdoc.fr/item/MAIS_2012_19_2_a8/

[1] C. Baier, J.-P. Katoen, Principles of model checking, The MIT Press, Cambridge, Massachusetts, London, England, 2008 | MR

[2] C. Courcoubetis, M. Yannakakis, “The complexity of probabilistic verification”, J. ACM, 42:4 (1995), 857–907 | DOI | MR | Zbl

[3] M. Dekhtyar, A. Dikovsky, M. Valiev, “On complexity of verification of interacting agents behavior”, Annals of pure and applied logic, 141 (2006), 336–362 | DOI | MR | Zbl

[4] M. Dekhtyar, A. Dikovsky, M. Valiev, “Temporal Verification of Probabilistic Multi-Agent Systems. Pillars of Computer Science”, Essays Dedicated to Boris (Boaz)Trakhtenbrot on the Occasion of His 85th Birthday, LNCS, 4800, 2008, 256–265 | MR

[5] H. Hansson, B. Jonsson, “A logic for reasoning about time and reliability”, Formal Aspects of Computing, 1994, 512–535 | DOI | Zbl

[6] Marta Kwiatkowska, “Model checking for probability and time: from theory to practice”, Proc. 18th IEEE Symposium on Logic in Computer Science (LICS'03), IEEE Computer Society Press, 2003, 351–360

[7] Luka de Alfaro, Formal verification of probabilistic systems, PhD, Stanford Univ., 1997 | Zbl

[8] E. M. Klark, O. Gramberg, D. Peled, Verifikatsiya modelei programm: Model Checking, MTsNMO, M., 2002

[9] P. V. Lebedev, “Programma verifikatsii veroyatnostnykh mnogoagentnykh sistem”, Trudy XII Natsionalnoi konferentsii po iskusstvennomu intellektu s mezhdunarodnym uchastiem, v. 4, Fizmatlit, M., 2010, 81–88