Instruction sequence size complexity of parity
From MaRDI portal
(Redirected from Publication:4589250)
Abstract: Each Boolean function can be computed by a single-pass instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. Auxiliary Boolean registers are not necessary for this. In the current paper, we show that, in the case of the parity functions, shorter instruction sequences are possible with the use of an auxiliary Boolean register in the presence of instructions to complement the content of auxiliary Boolean registers. This result supports, in a setting where programs are instruction sequences acting on Boolean registers, a basic intuition behind the storage of auxiliary data, namely the intuition that this makes possible a reduction of the size of a program.
Recommendations
- On instruction sets for Boolean registers in program algebra
- A short introduction to program algebra with instructions for Boolean registers
- On algorithmic equivalence of instruction sequences for computing bit string functions
- scientific article; zbMATH DE number 5077425
- On the parity complexity measures of Boolean functions
Cited in
(4)- On the complexity of the correctness problem for non-zeroness test instruction sequences
- A short introduction to program algebra with instructions for Boolean registers
- On algorithmic equivalence of instruction sequences for computing bit string functions
- On instruction sets for Boolean registers in program algebra
This page was built for publication: Instruction sequence size complexity of parity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589250)
