A probabilistic PDL

Dexter Kozen

1983 · 115 citations · 9 references

DOIFull text

Open access

Concepts

Abstract

In this paper we give a probabilistic analog PPDL of Propositional Dynamic Logic. We prove a small model property and give a polynomial space decision procedure for formulas involving well-structured programs. We also give a deductive calculus and illustrate its use by calculating the expected running time of a simple random walk program.

References

9