Affiliations: [a] Informatics Institute, University of Amsterdam Science Park 904, 1098 XH Amsterdam, the Netherlands {J.A.Bergstra,C.A.Middelburg}@uva.nl
Correspondence:
[*]
Address for correspondence: Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands.
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. The work presented in this paper is carried out in the setting of PGA (ProGram Algebra)
Keywords: Boolean function family, instruction sequence size, non-uniform complexity measure, parity function
