Abstract interpretation of programs as Markov decision processesReportar como inadecuado

Abstract interpretation of programs as Markov decision processes - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIENS - Laboratoire d-informatique de l-école normale supérieure

Abstract : We propose a formal language for the specification of trace properties of probabilistic, nondeterministic transition systems, encompassing the properties expressible in Linear Time Logic. Those formulas are in general undecidable on infinite deterministic transition systems and thus on infinite Markov decision processes. This language has both a semantics in terms of sets of traces, as well as another semantics in terms of measurable functions; we give and prove theorems linking the two semantics. We then apply abstract interpretation-based techniques to give upper bounds on the worst-case probability of the studied property. We propose an enhancement of this technique when the state space is partitioned — for instance along the program points — allowing the use of faster iteration methods.

Keywords : program semantics probabilities nondeterminism abstract interpretation

Autor: David Monniaux -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados