Instruction Sequence Size Complexity of Parity

• Autorzy: Bergstra J. A. , Middelburg C. A.

Identyfikatory

DOI

10.3233/FI-2016-1450

• Języki publikacji: EN

Abstrakty

EN

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).

Słowa kluczowe

EN

Boolean function family; instruction sequence size; non-uniform complexity measure; parity function

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 3
• Strony: 297--309
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Bergstra J. A.

• Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands

autor

Middelburg C. A.

• Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands

Bibliografia

• [1] Bergstra JA, Middelburg CA. Instruction Sequence Based Non-uniform Complexity Classes. Scientific Annals of Computer Science. 2014;24(1):47–89. doi:10.7561/SACS.2014.1.47.
• [2] Salomon D. Coding for Data and Computer Communications. Berlin: Springer-Verlag; 2005. doi:10.1007/b102531.
• [3] Furst M, Saxe JB, Sipser M. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory. 1984;17(1):13–27. doi:10.1007/BF01744431.
• [4] Håstad J. Almost Optimal Lower Bounds for Small Depth Circuits. In: STOC ’86. ACM Press; 1986. p. 6–20. doi:10.1145/12130.12132.
• [5] Wegener I. The Complexity of the Parity Function in Unbounded Fan-In, Unbounded Depth Circuits. Theoretical Computer Science. 1991;85(1):155–170. doi:10.1016/0304-3975(91)90052-4.
• [6] Beame P, Impagliazzo R, Srinivasan S. Approximating AC0 by Small Height Decision Trees and a Deterministic Algorithm for #AC0SAT. In: CCC 2012. IEEE Computer Society Press; 2012. p. 117–125. doi:10.1109/CCC.2012.40.
• [7] Impagliazzo R, Matthews W, Paturi R. A Satisfiability Algorithm for AC0. In: SODA 2012. SIAM; 2012. p. 961–972. doi:10.1137/1.9781611973099.77.
• [8] Håstad J. On the Correlation of Parity and Small-Depth Circuits. SIAM Journal of Computing. 2014;43(5):1699–1708. doi:10.1137/120897432.
• [9] Bergstra JA, Middelburg CA. On Instruction Sets for Boolean Registers in Program Algebra. Scientific Annals of Computer Science. 2016; 26(1):1–26. doi:10.7561/SACS.2016.1.1.
• [10] Böhm C, Jacopini G. Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules. Communications of the ACM. 1966;9(5):366–371. doi:10.1145/355592.365646.
• [11] Cooper DC. Böhm and Jacopini’s Reduction of Flow Charts. Communications of the ACM. 1967; 10(8):463, 473. doi:10.1145/363534.363539.
• [12] Owicki S, Gries D. An Axiomatic Proof Technique for Parallel Programs I. Acta Informatica. 1976;6(4):319–340. doi:10.1007/BF00268134.
• [13] Apt KR, de Boer FS, Olderog ER. Verification of Sequential and Concurrent Programs. 3rd ed. Texts in Computer Science. Berlin: Springer-Verlag; 2009. doi:10.1007/978-1-84882-745-5.
• [14] Bergstra JA, Loots ME. Program Algebra for Sequential Code. Journal of Logic and Algebraic Programming. 2002;51(2):125–156. doi:10.1016/S1567-8326(02)00018-8.
• [15] Bergstra JA, Middelburg CA. Instruction Sequences for Computer Science. vol. 2 of Atlantis Studies in Computing. Amsterdam: Atlantis Press; 2012. doi:10.2991/978-94-91216-65-7.
• [16] Bergstra JA, Middelburg CA. On Algorithmic Equivalence of Instruction Sequences for Computing Bit String Functions. Fundamenta Informaticae. 2015; 138(4):411–434. doi:10.3233/FI-2015-1219.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).