On algorithmic equivalence of instruction sequences for computing bit string functions

DOI10.3233/FI-2015-1219zbMATH Open1334.68313arXiv1402.4950OpenAlexW1569457587MaRDI QIDQ2804184FDOQ2804184

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

Publication date: 28 April 2016

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

single-pass instruction sequencebit string functionstructural algorithmic equivalencestructural computational equivalence

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cited In (6)

• Quantitative expressiveness of instruction sequence classes for computation on single bit registers
• Instruction sequence size complexity of parity
• On the complexity of the correctness problem for non-zeroness test instruction sequences
• A theory of computer instructions
• Instruction sequences expressing multiplication algorithms
• On instruction sets for Boolean registers in program algebra

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)