On algorithmic equivalence of instruction sequences for computing bit string functions
From MaRDI portal
Abstract: Every partial function from bit strings of a given length to bit strings of a possibly different given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We look for an equivalence relation on instruction sequences of this kind that captures to a reasonable degree the intuitive notion that two instruction sequences express the same algorithm.
Recommendations
- Instruction sequences expressing multiplication algorithms
- Instruction sequence size complexity of parity
- On instruction sets for Boolean registers in program algebra
- Quantitative expressiveness of instruction sequence classes for computation on single bit registers
- A short introduction to program algebra with instructions for Boolean registers
Cited in
(6)- On the complexity of the correctness problem for non-zeroness test instruction sequences
- Quantitative expressiveness of instruction sequence classes for computation on single bit registers
- A theory of computer instructions
- Instruction sequence size complexity of parity
- On instruction sets for Boolean registers in program algebra
- Instruction sequences expressing multiplication algorithms
This page was built for publication: On algorithmic equivalence of instruction sequences for computing bit string functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804184)
