A short introduction to program algebra with instructions for Boolean registers

zbMATH Open1445.68049arXiv1808.04264MaRDI QIDQ2209486FDOQ2209486

Authors: C. A. Middelburg, J. A. Bergstra 

Publication date: 2 November 2020

Published in: Computer Science Journal of Moldova (Search for Journal in Brave)

Abstract: A parameterized algebraic theory of instruction sequences, objects that represent the behaviours produced by instruction sequences under execution, and objects that represent the behaviours exhibited by the components of the execution environment of instruction sequences is the basis of a line of research in which issues relating to a wide variety of subjects from computer science have been rigorously investigated thinking in terms of instruction sequences. In various papers that belong to this line of research, use is made of an instantiation of this theory in which the basic instructions are instructions to read out and alter the content of Boolean registers and the components of the execution environment are Boolean registers. In this paper, we give a simplified presentation of the most general such instantiated theory.

Full work available at URL: https://arxiv.org/abs/1808.04264

Recommendations

• On instruction sets for Boolean registers in program algebra
• Program algebra for Turing-machine programs
• Instruction sequence size complexity of parity
• On the behaviours produced by instruction sequences under execution
• A theory of computer instructions

zbMATH Keywords

program algebrathread algebraBoolean registerthread-service interaction

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Logic in computer science (03B70) Semantics in the theory of computing (68Q55)

Cited In (10)

• On the expressiveness of single-pass instruction sequences
• Instruction sequence size complexity of parity
• Axioms for behavioural congruence of single-pass instruction sequences
• Program algebra for random access machine programs
• A theory of computer instructions
• On algorithmic equivalence of instruction sequences for computing bit string functions
• Program algebra for Turing-machine programs
• On the behaviours produced by instruction sequences under execution
• An instruction sequence semigroup with involutive anti-automorphisms
• On instruction sets for Boolean registers in program algebra

This page was built for publication: A short introduction to program algebra with instructions for Boolean registers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2209486)