ComputingComputer ScienceMathematicsAlgorithmsLogicProbability TheoryAutomated ReasoningPredicate LogicDynamic LogicDynamic Logic ModelsPolynomial SpaceProbabilistic LogicProbabilistic Model CheckingPropositional CalculusSimple Random Walk
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.
9
M. S. Ramanujan, Helmut Schaefer · American Mathematical Monthly · 1967 · 4K citations
Semantics of probabilistic programs
Dexter Kozen · Journal of Computer and System Sciences · 1981 · 507 citations
Reasoning with time and chance
Daniel Lehmann, Saharon Shelah · Information and Control · 1982 · 137 citations
On the extremely fair treatment of probabilistic algorithms
Amir Pnueli · 1983 · 94 citations