|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.|
|Copyright||The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1986/CS/CS0394), 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