166
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      Proof rules for probabilistic loops

      *

      Proceedings of the BCS-FACS 7th Refinement Workshop (RW)

      BCS-FACS 7th Refinement Workshop

      3-5 July 1996

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Probabilistic predicate transformers provide a semantics for imperative programs containing both demonic and probabilistic nondeterminism. Like the (standard) predicate transformers popularised by Dijkstra, they model programs as functions from final results to the initial conditions suffcient to achieve them.

          This paper presents practical proof rules, using the probabilistic transformers, for reasoning about iterations when probability is present. They are thoroughly illustrated by example: probabilistic binary chop, faulty factorial, the martingale gambling strategy and Herman’s probabilistic self-stabilisation.

          Just as for traditional programs, weakest-precondition based proof rules for program derivation are an important step on the way to designing more general refinement techniques, or even a refinement calculus, for imperative probabilistic programming.

          Related collections

          Author and article information

          Conference
          July 1996
          July 1996
          : 1-19
          Affiliations
          [* ]Morgan is a member of the Probabilistic Systems Group within the Programming Research Group at Oxford University: the other members are Annabelle McIver, Jeff Sanders and Karen Seidel. Our work is supported by the EPSRC.
          Article
          10.14236/ewic/RW1996.10
          © Carroll Morgan. Published by BCS Learning and Development Ltd. Proceedings of the BCS-FACS 7th Refinement Workshop, Bath

          This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

          Proceedings of the BCS-FACS 7th Refinement Workshop
          RW
          7
          Bath
          3-5 July 1996
          Electronic Workshops in Computing (eWiC)
          BCS-FACS 7th Refinement Workshop
          Product
          Product Information: 1477-9358BCS Learning & Development
          Self URI (journal page): https://ewic.bcs.org/
          Categories
          Electronic Workshops in Computing

          Comments

          Comment on this article