Skip to main content
Springer Nature Link
Log in

Relative complexity of operations on numeric and bit-string algebras

  • Published:
Save article
View saved research
Mathematical systems theory Aims and scope Submit manuscript

Abstract

Sets of primitive operations for algebras with numerical and bit string domains are classified according to their computational efficiency. The relative complexity of certain basic operations on such algebras is determined.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from €37.37 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price includes VAT (Netherlands)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. N. A. Lynch and E. K. Blum, Relative Complexity of Algebras, (to be published).

  2. N. A. Lynch and E. K. Blum, Efficient Reducibility Between Programming Systems,Proceedings of Ninth Annual Symposium on Theory of Computation, ACM, Boulder, 228–238 (1977).

  3. A. Chandra, Efficient Compilation of Linear Recursive Programs,14th Annual Symposium on Switching and Automata Theory, October 15–17, 16–25 (1973).

  4. D. Kfoury, Comparing Algebraic Structures up to Algorithmic Equivalence in Automata,Languages and Programming, Ed. M. Nivat, North-Holland/ Elsevier, 253–263 (1973). See also Translatability of Schemes over Restricted Interpretations,J. Comp. and Syst. Sciences 8, 387–408 (1974).

    Google Scholar 

  5. A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company, 1976.

  6. P. Fischer, A. Meyer, and A. Rosenberg, Real-time Simulation of Multihead Tape Units,JACM 19, 590–607, (1972).

    Google Scholar 

  7. B. Leong and J. Seiferas, New Real-time Simulations of Multilevel Tape Units.Ninth Annual Symposium on Theory of Computation, ACM, Boulder, 239–247 (1977).

  8. N. A. Lynch, Straight-Line Program Length as a Parameter for Complexity Measures,Theoretical Computer Science, (to appear). Also seeProceedings of Tenth Annual ACM Symposium on Theory of Computing, San Diego, 150–161, (1978).

  9. L. J. Stockmeyer, Arithmetic Versus Boolean Operations in Idealized Register Machines,IBM RC 5954, (A 25 837).

  10. N. A. Lynch and E. K. Blum, A Difference in Expressive Power Between Flowcharts and Recursion Schemes,Mathematics Systems Theory 12, 205–211 (1979).

    Google Scholar 

  11. G. Grätzer,Universal Algebra, Van Nostrand, Princeton, N.J., 1968.

    Google Scholar 

  12. P. M. Cohn,Universal Algebra, Harper and Row, N.Y., 1965.

    Google Scholar 

  13. A. I. Malcev,Algebraic Systems, Springer-Verlag, N.Y., 1973.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Information and Computer Science, Georgia Institute of Technology, 30332, Atlanta, Georgia, USA

    Nancy Lynch

  2. Department of Mathematics, University of Southern California, 90007, Los Angeles, California, USA

    Edward K. Blum

Authors
  1. Nancy Lynch
    View author publications

    Search author on:PubMed Google Scholar

  2. Edward K. Blum
    View author publications

    Search author on:PubMed Google Scholar

Additional information

This research was partially supported by NSF Grant DCR75-02373.

This research was partially supported by NSF Grant MCS77-15628 and MCS78-01689.

This research was partially supported by NSF Grant MCS78-07461.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lynch, N., Blum, E.K. Relative complexity of operations on numeric and bit-string algebras. Math. Systems Theory 13, 187–207 (1979). https://doi.org/10.1007/BF01744295

Download citation

  • Received:

  • Revised:

  • Issue date:

  • DOI: https://doi.org/10.1007/BF01744295

Keywords