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