Program algebra with a jump-shift instruction

DOI10.1016/J.JAL.2008.07.001MaRDI QIDQ959050zbMATH OpenOpenAlexFDO

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

Publication date 11 December 2008

Published in Journal of Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

program algebrathread algebraexecution mechanismjump-shift instructionthread extraction

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Abstract: We study sequential programs that are instruction sequences with jump-shift instructions in the setting of PGA (ProGram Algebra). Jump-shift instructions preceding a jump instruction increase the position to jump to. The jump-shift instruction is not found in programming practice. Its merit is that the expressive power of PGA extended with the jump-shift instruction, is not reduced if the reach of jump instructions is bounded. This is used to show that there exists a finite-state execution mechanism that by making use of a counter can produce each finite-state thread from some program that is a finite or periodic infinite sequence of instructions from a finite set.

Recommendations

• Program algebra for sequential code
• Program algebra for component code
• Program algebra with unit instruction operators
• Logical Approaches to Computational Barriers
• Instruction sequences with indirect jumps

Cites work

• scientific article; zbMATH DE number 1142323 (Why is no real title available?)
• scientific article; zbMATH DE number 2038694 (Why is no real title available?)
• scientific article; zbMATH DE number 1368948 (Why is no real title available?)
• scientific article; zbMATH DE number 1412988 (Why is no real title available?)
• Combining programs and state machines
• Instruction sequences with dynamically instantiated instructions
• Instruction sequences with indirect jumps
• Logical Approaches to Computational Barriers
• Program algebra for sequential code
• Thread algebra for strategic interleaving
• Thread algebra with multi-level strategies

Cited in

(8)

• Program algebra with unit instruction operators
• On the contribution of backward jumps to instruction sequence expressiveness
• On the expressiveness of single-pass instruction sequences
• Instruction sequence processing operators
• Program algebra for component code
• Program algebra for sequential code
• An instruction sequence semigroup with involutive anti-automorphisms
• Instruction sequences with indirect jumps

This page was built for publication: Program algebra with a jump-shift instruction

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