Relative complexity of algebras.

*(English)*Zbl 0473.68031##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68N01 | General topics in the theory of software |

PDF
BibTeX
XML
Cite

\textit{N. A. Lynch} and \textit{E. K. Blum}, Math. Syst. Theory 14, 193--214 (1981; Zbl 0473.68031)

Full Text:
DOI

**OpenURL**

##### References:

[1] | C. C. Elgot, Monadic Computation and Iterative Algebraic Theories, IBM Report RC 4564, October 1973. · Zbl 0327.02040 |

[2] | B. H. Liskov and S. N. Zilles, Specification Techniques for Data Abstractions, Software Engineering, Vol. SE-1, No. 1, 7–19, March 1975. |

[3] | F. L. Morris, Correctness of Translations of Programming Languages–An Algebraic Approach, Stanford U. Report CS-72-303, August 1972. |

[4] | R. M. Burstall, An Algebraic Description of Programs with Assertions, Verification and Simulation, in Proc. ACM Conference on Proving Assertions about Programs, SIGPLAN Notices 7, 1, ACM 72. |

[5] | G. Birkhoff, The Role of Algebra in Computing, in Computers in Algebra and Number Theory, Vol. IV SIAM-AMS Proc. A.M.S., 1971. · Zbl 0241.68003 |

[6] | J. A. Goguen, J. W. Thatcher, E. G. Wagner and J. B. Wright, A Junction between Computer Science and Category Theory: I Basic Concepts and Examples, Part 1, IBM Report RC-4526 (September 1973); Part 2, IBM Report RC-5908 (March 1976). |

[7] | R. M. Burstall and J. W. Thatcher, The Algebraic Theory of Recursive Program Schemes, Symposium on Category Theory Applied to Computation and Control, Lecture Notes in Computer Science 25, 126–131, (1975). · Zbl 0363.68035 |

[8] | J. B. Wright, J. A. Goguen, J. W. Thatcher and E. G. Wagner, Rational Algebraic Theories and Fixed-Point Solutions, Proc. 17th Annual Symposium on Foundations of Computer Science, 147–158, (October 1976). |

[9] | J. V. Guttag, E. Horowitz and D. R. Musser, Abstract Data Types and Software Validation. Research Report 76–48. Information Sciences Institute, August 1976. · Zbl 0387.68012 |

[10] | J. A. Goguen, J. W. Thatcher and E. G. Wagner, An Initial Algebra Approach to the Specification, Correctness and Implementation of Abstract Data Types, IBM Thomas J. Watson Research Center, manuscript. |

[11] | A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. · Zbl 0326.68005 |

[12] | S. A. Cook, The Complexity of Theorem-Proving Procedures, Third Annual ACM Symposium on Theory of Computing, 151–158, 1971. · Zbl 0253.68020 |

[13] | R. Karp, Reducibility among Combinatorial Problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, 85–104, (1972). |

[14] | R. Ladner, N. A. Lynch and A. L. Selman, Comparison of Polynomial-Time Reducibilities, Sixth Annual ACM Symposium on Theory of Computing, 110–121, 1974. · Zbl 0381.68041 |

[15] | E. K. Blum and D. R. Estes, A Generalization of the Homomorphism Concept, Algebra Universalis, July, 1977. |

[16] | N. A. Lynch, Straight-Line Program Length as a Parameter for Complexity Measures. Tenth Annual ACM Symposium on Theory of Computing, 1978. · Zbl 1282.03021 |

[17] | N. A. Lynch, Straight-Line Program as a Parameter for Complexity Analysis, to appear in Theoretical Computer Science. · Zbl 0458.68008 |

[18] | N. A. Lynch and E. K. Blum, A Difference in Expressive Power Between Flowcharts and Recursion Schemes, Math. Syst. Theory, 205–211, 1979. · Zbl 0425.68020 |

[19] | N. A. Lynch and E. K. Blum, Relative Complexity of Operation Sets for Numeric and Bit String Algebras, Math. Syst. Theory 13, 187–207 (1980). · Zbl 0469.68046 |

[20] | N. A. Lynch and E. K. Blum, Efficient Reducibility Between Programming Systems, Proceedings of Ninth Annual Symposium on Theory of Computation, 1977. |

[21] | A. Cremers and T. Hibbard, Formal Modelling of Virtual Machines. To appear in IEEE Transactions on Software Engineering. · Zbl 0385.68008 |

[22] | R. Lipton, S. Eisentat, and R. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures, JACM, Vol. 23, No. 4, October 1976. · Zbl 0333.68024 |

[23] | R. Rivest, L. Adleman, and M. Dertouzos, On Data Banks and Privacy Homomorphisms, in Foundations of Secure Computation, Academic Press, Inc., 171–179, 1978. |

[24] | A. Chandra, Efficient Compilation of Linear Recursive Programs, Stanford Artificial Intelligence Project MEMO AIM-167, April 1972. |

[25] | D. Kfoury, Comparing Algebraic Structures up to Algorithmic Equivalence. In Automata, Languages and Programming, Ed. M. Nivat, North-Holland/Elsevier, 253–263, 1973. · Zbl 0281.68007 |

[26] | M. S. Paterson and C. E. Hewitt, Comparative Schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation 119–128, (1970). |

[27] | J. Guttag, The Specification and Application to Programming of Abstract Data Types, University of Toronto, Computer Systems Research Group, Technical Report CSRG-59, September 1975. |

[28] | H. R. Strong and S. A. Walker, Characterization of Flowchartable Recursions in Fourth Annual ACM Symposium on Theory of Computing, May 1972. |

[29] | H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. · Zbl 0183.01401 |

[30] | K. Weihrauch, On the Computational Complexity of Program Schemata, Cornell University Department of Computer Science, TR 74–196, February 1974. · Zbl 0288.68018 |

[31] | D. Knuth, The Art of Computer Programming, 2, Fundamental Algorithms, Addison-Wesley, 1968. · Zbl 0191.17903 |

[32] | A. Schönhage, Real-Time Simulation of Multi-Dimensional Turing Machines by Storage, Modification Machines, Project MAC Technical Memorandum 7, MIT (1973). |

[33] | R. E. Tarjan, Reference Machines Require Non-Linear Time to Maintain Disjoint Sets, in 9th Annual ACM Symposium on Theory of Computing, May 1977. |

[34] | A. L. Rosenberg, Data Encodings and Their Costs, Acta Inform. 9, 273–292, (1978). · Zbl 0434.68048 |

[35] | G. Grätzer, Universal Algebra, Van Nostrand, 1968. |

[36] | P. Cohn, Universal Algebra, Harper and Row, 1965. |

[37] | A. Borodin, L. J. Guibas, N. A. Lynch and A. C. Yao, Efficient Searching via Partial Ordering, submitted for publication. · Zbl 0457.68056 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.