Technical Report CS0394

Title: Decidability Questions for Finite Probabilistic Propositional Dynamic Logic
Authors: M.L. Tiornkin and J.A. Makowsky
Abstract: This paper deals with various versions of finite propositional-probabilistic dynamic logic. Besides the logics previously introduced in the literature [Fe, Ko79, Ko83] we present some natural variations and extensions of these logics. We also present another kind of probabilistic propositional dynamic logic with simple probabilistic estimations and "almost regular" program language. We investigate the (un)decidability of these logics and present a complete picture of decidability and undecidability. Some of these logics have the finite model property, and therefore, if they are undecidable. they are exactly Pi01. We show that allowing nesting and probabilistic choice leads to undecidability.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1986
To the main CS technical reports page

Computer science department, Technion