Program algebra with a jump-shift instruction
arXiv:0712.1658 · doi:10.1016/j.jal.2008.07.001
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.
19 pages
References in corpus (2)
Cited by in corpus (13)
- Thread extraction for polyadic instruction sequences
- Instruction sequence processing operators
- On algorithmic equivalence of instruction sequences for computing bit string functions
- Instruction sequences and non-uniform complexity theory
- Putting Instruction Sequences into Effect
- On the expressiveness of single-pass instruction sequences
- Autosolvability of halting problem instances for instruction sequences
- Transmission protocols for instruction streams
- Instruction sequence notations with probabilistic instructions
- Functional units for natural numbers
- Probabilistic thread algebra
- Instruction sequences for the production of processes
- A protocol for instruction stream processing