Algebras for Iteration, Infinite Executions and Correctness of Sequential Computations

 Title: Algebras for Iteration, Infinite Executions and Correctness of Sequential Computations Author: Walter Guttmann Submission date: 2021-10-12 Abstract: We study models of state-based non-deterministic sequential computations and describe them using algebras. We propose algebras that describe iteration for strict and non-strict computations. They unify computation models which differ in the fixpoints used to represent iteration. We propose algebras that describe the infinite executions of a computation. They lead to a unified approximation order and results that connect fixpoints in the approximation and refinement orders. This unifies the semantics of recursion for a range of computation models. We propose algebras that describe preconditions and the effect of while-programs under postconditions. They unify correctness statements in two dimensions: one statement applies in various computation models to various correctness claims. BibTeX: @article{Correctness_Algebras-AFP, author = {Walter Guttmann}, title = {Algebras for Iteration, Infinite Executions and Correctness of Sequential Computations}, journal = {Archive of Formal Proofs}, month = oct, year = 2021, note = {\url{https://isa-afp.org/entries/Correctness_Algebras.html}, Formal proof development}, ISSN = {2150-914x}, } License: BSD License Depends on: MonoBoolTranAlgebra, Stone_Kleene_Relation_Algebras, Subset_Boolean_Algebras Status: [ok] This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.