On Instruction Sets for Boolean Registers in Program Algebra

Published in Volume XXVI, Issue 1, 2016, pages 1-26, doi: 10.7561/SACS.2016.1.1

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

Abstract

In previous work carried out in the setting of program algebra, including work in the area of instruction sequence size complexity, we chose instruction sets for Boolean registers that contain only instructions of a few of the possible kinds. In the current paper, we study instruction sequence size bounded functional completeness of all  possible instruction sets for Boolean registers. We expect that the results of this study will turn out to be useful to adequately assess results of work that is concerned with lower bounds of instruction sequence size complexity.

Full Text (PDF)

References

[1] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge, 2009.

[2] J. A. Bergstra and M. E. Loots. Program algebra for sequential code. Journal of Logic and Algebraic Programming, 51(2):125-156, 2002. doi: 10.1016/S1567-8326(02)00018-8.

[3] J. A. Bergstra and C. A. Middelburg. Instruction sequence processing operators. Acta Informatica, 49(3):139-172, 2012. doi:10.1007/ s00236-012-0154-2.

[4] J. A. Bergstra and C. A. Middelburg. Instruction Sequences for Computer Science, volume 2 of Atlantis Studies in Computing. Atlantis Press, Amsterdam, 2012. doi:10.2991/978-94-91216-65-7.

[5] J. A. Bergstra and C. A. Middelburg. Instruction sequence based non-uniform complexity classes. Scientific Annals of Computer Science, 24(1):47-89, 2014. doi:10.7561/SACS.2014.1.47.

[6] J. A. Bergstra and C. A. Middelburg. Instruction sequence size complexity of parity. arXiv:1412.6787v2 [cs.CC], 2014. To appear in Fundamenta Informaticae.

[7] J. A. Bergstra and C. A. Middelburg. On algorithmic equivalence of instruction sequences for computing bit string functions. Fundamenta Informaticae, 138(4):411-434, 2015. doi:10.3233/FI-2015-1219.

[8] H. Ehrig and B. Mahr. Fundamentals of Algebraic Specification I: Equations and Initial Semantics, volume 6 of EATCS Monographs. Springer-Verlag, Berlin, 1985. doi:10.1007/978-3-642-69962-7.

[9] W. A. Hodges. Model Theory, volume 42 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 1993.

[10] S. Homer and A. L. Selman. Computability and Complexity Theory. Springer-Verlag, Berlin, second edition, 2011. doi:10.1007/ 978-1-4614-0682-2.

[11] C. A. Middelburg. Instruction sequences as a theme in computer science. https://instructionsequence.wordpress.com/, 2015.

[12] D. Sannella and A. Tarlecki. Algebraic preliminaries. In E. Astesiano, H.-J. Kreowski, and B. Krieg-Brückner, editors, Algebraic Foundations of Systems Specification, pages 13-30. Springer-Verlag, Berlin, 1999. doi:10.1007/978-3-642-59851-7_2.

[13] D. Sannella and A. Tarlecki. Foundations of Algebraic Specification and Formal Software Development. Monographs in Theoretical Computer Science, An EATCS Series. Springer-Verlag, Berlin, 2012. doi:10. 1007/978-3-642-17336-3.

[14] I. Wegener. Complexity Theory – Exploring the Limits of Efficient Algorithms. Springer-Verlag, Berlin, 2005. doi:10.1007/3-540-27477-4.

[15] M. Wirsing. Algebraic specification. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 675-788. Elsevier, Amsterdam, 1990.

Bibtex

@article{sacscuza:bergstra2016oisfbripa,
  title={On Instruction Sets for Boolean Registers in Program Algebra},
  author={J.A. Bergstra and C.A. Middelburg},
  journal={Scientific Annals of Computer Science},
  volume={26},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2016},
  pages={1--26},
  doi={10.7561/SACS.2016.1.1},
  publisher={``A.I. Cuza'' University Press}
}