256
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-article
      *
      Proceedings of the BCS-FACS 7th Refinement Workshop (RW)
      BCS-FACS 7th Refinement Workshop
      3-5 July 1996
      Bookmark

            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.

            Content

            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
            1f83535e-bca8-4ae9-9e6a-aa6151fa84d9
            © 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 (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/RW1996.10
            Self URI (journal page): https://ewic.bcs.org/
            Categories
            Electronic Workshops in Computing

            Applied computer science,Computer science,Security & Cryptology,Graphics & Multimedia design,General computer science,Human-computer-interaction

            Comments

            Comment on this article