On Algorithmic Equivalence of Instruction Sequences for Computing Bit String Functions

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

Identyfikatory

DOI

10.3233/FI-2015-1219

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

structural algorithmic equivalence; structural computational equivalence; single pass instruction sequence; bit string function

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 4
• Strony: 411--434
• Opis fizyczny: Bibliogr. 23 poz., tab.

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, J. A., Bethke, I.: Polarized Process Algebra and Program Equivalence, Proceedings 30th ICALP (J. C. M. Baeten, J. K. Lenstra, J. Parrow, G. J. Woeginger, Eds.), vol. 2719 of Lecture Notes in Computer Science, Springer-Verlag, 2003, 1–21.
• [2] Bergstra, J. A., Bethke, I.: Predictable and Reliable Program Code: Virtual Machine Based Projection Semantics, in: Handbook of Network and Systems Administration (J. A. Bergstra, M. Burgess, Eds.), Elsevier, Amsterdam, 2007, 653–685.
• [3] Bergstra, J. A., Loots, M. E.: Program Algebra for Sequential Code, Journal of Logic and Algebraic Programming, 51(2), 2002, 125–156.
• [4] Bergstra, J. A.,Middelburg, C. A.: ProgramAlgebra with a Jump-Shift Instruction, Journal of Applied Logic, 6(4), 2008, 553–563.
• [5] Bergstra, J. A., Middelburg, C. A.: Instruction Sequence Processing Operators, Acta Informatica, 49(3), 2012, 139–172.
• [6] Bergstra, J. A., Middelburg, C. A.: Instruction Sequences for Computer Science, vol. 2 of Atlantis Studies in Computing, Atlantis Press, Amsterdam, 2012.
• [7] Bergstra, J. A., Middelburg, C. A.: Instruction Sequence Expressions for the Karatsuba Multiplication Algorithm, arXiv:1312.1529v1 [cs.PL], December 2013.
• [8] Bergstra, J. A., Middelburg, C. A.: Instruction Sequence Expressions for the Secure Hash Algorithm SHA-256, arXiv:1308.0219v5 [cs.PL], August 2013.
• [9] Bergstra, J. A., Middelburg, C. A.: Long Multiplication by Instruction Sequences with Backward Jump Instructions, arXiv:1312.1812v3 [cs.PL], December 2013.
• [10] Bergstra, J. A., Middelburg, C. A.: Instruction Sequence Based Non-uniform Complexity Classes, Scientific Annals of Computer Science, 24(1), 2014, 47–89.
• [11] Berry, G., Curien, P. L.: Sequential Algorithms on Concrete Data Structures, Theoretical Computer Science, 20(3), 1982, 265–321.
• [12] Blass, A., Dershowitz, N., Gurevich, Y.: When Are Two Algorithms the Same?, The Bulletin of Symbolic Logic, 15(2), 2009, 145–168.
• [13] Dean, W.: What Algorithms Could Not Be, Ph.D. Thesis, Rutgers, The State University of New Jersey, New Brunswick, NJ, 2007.
• [14] van Glabbeek, R. J.: The Linear Time – Branching Time Spectrum I, in: Handbook of Process Algebra (J. A. Bergstra, A. Ponse, S. A. Smolka, Eds.), Elsevier, Amsterdam, 2001, 3–99.
• [15] Gurevich, Y.: Sequential Abstract-State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, 1(1), 2000, 77–111.
• [16] Kolmogorov, A. N., Uspensky, V. A.: On the Definition of an Algorithm, Uspekhi Matematicheskikh Nauk, 13(4(82)), 1958, 3–28, In Russian.
• [17] Metzger, R. C., Wen, Z.: Automatic Algorithm Recognition and Replacement: A New Approach to Program Optimization, MIT Press, Cambridge,MA, 2000.
• [18] Milner, R.: An Algebraic Definition of Simulation Between Programs, IJCAI ’71, Morgan Kaufmann, San Francisco, 1971, 481–489.
• [19] Moschovakis, Y. N.: What Is an Algorithm?, in: Mathematics Unlimited – 2001 and Beyond (B. Engquist, W. Schmid, Eds.), Springer-Verlag, Berlin, 2001, 919–936.
• [20] Sannella, D., Tarlecki, A.: Algebraic Preliminaries, in: Algebraic Foundations of Systems Specification (E. Astesiano, H.-J. Kreowski, B. Krieg-Br¨uckner, Eds.), Springer-Verlag, Berlin, 1999, 13–30.
• [21] Uspensky, V. A., Semenov, A. L.: What Are the Gains of the Theory of Algorithms, Algorithms in Modern Mathematics and Computer Science (A. P. Ershov, D. E. Knuth, Eds.), vol. 122 of Lecture Notes in Computer Science, Springer-Verlag, 1981, 100–234.
• [22] Wirsing,M.: Algebraic Specification, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier, Amsterdam, 1990, 675–788.
• [23] Yanofsky, N. S.: Towards a Definition of an Algorithm, Journal of Logic and Computation, 21(2), 2011, 253–286.