Relating direct and predicate transformer partial correctness semantics for an imperative probabilistic-nondeterministic language
Saved in:
| Title: | Relating direct and predicate transformer partial correctness semantics for an imperative probabilistic-nondeterministic language |
|---|---|
| Authors: | Keimel, K., Rosenbusch, A. artus.ph.rosenbusch@gmail.com, Streicher, T. |
| Source: | Theoretical Computer Science. Jun2011, Vol. 412 Issue 25, p2701-2713. 13p. |
| Subjects: | Imperative programming, Denotational semantics, Predicate (Logic), Duality theory (Mathematics), Probability theory, Mathematical invariants, Isomorphism (Mathematics) |
| Abstract: | Abstract: In Keimel et al. (2009) we have systematically derived a predicate transformer semantics from a direct semantics in total correctness style for a nondeterministic/probabilistic basic imperative programming language . In the current paper we perform the analogous task starting from a direct semantics for in partial correctness style. As in we establish a “Minkowski duality” providing an isomorphism between direct semantics and a continuation semantics from which a predicate transformer semantics can be read off immediately. But has only an auxiliary status and we use it to define a predicate transformer as capturing the idea of “weakest liberal preexpectation” (in analogy with weakest liberal precondition). We further explain why of while-loops is computed as a greatest fixpoint and argue why this allows one to reason about while-loops in terms of invariants as opposed to the of while-loops as considered in for which this is impossible. [Copyright &y& Elsevier] |
| Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
