{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T05:16:45Z","timestamp":1648790205980},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1981,12,1]],"date-time":"1981-12-01T00:00:00Z","timestamp":376012800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1981,12]]},"DOI":"10.1007\/bf01752396","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T10:43:16Z","timestamp":1118832196000},"page":"193-214","source":"Crossref","is-referenced-by-count":6,"title":["Relative complexity of algebras"],"prefix":"10.1007","volume":"14","author":[{"given":"Nancy A.","family":"Lynch","sequence":"first","affiliation":[]},{"given":"Edward K.","family":"Blum","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01752396_CR1","unstructured":"C. C. Elgot, Monadic Computation and Iterative Algebraic Theories, IBM Report RC 4564, October 1973."},{"issue":"1","key":"BF01752396_CR2","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/TSE.1975.6312816","volume":"SE-1","author":"B. H. Liskov","year":"1975","unstructured":"B. H. Liskov and S. N. Zilles, Specification Techniques for Data Abstractions, Software Engineering, Vol. SE-1, No. 1, 7\u201319, March 1975.","journal-title":"Software Engineering"},{"key":"BF01752396_CR3","doi-asserted-by":"crossref","unstructured":"F. L. Morris, Correctness of Translations of Programming Languages\u2014An Algebraic Approach, Stanford U. Report CS-72-303, August 1972.","DOI":"10.21236\/ADA954771"},{"key":"BF01752396_CR4","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/942578.807068"},{"key":"BF01752396_CR5","unstructured":"G. Birkhoff, The Role of Algebra in Computing, in Computers in Algebra and Number Theory, Vol. IV SIAM-AMS Proc. A.M.S., 1971."},{"key":"#cr-split#-BF01752396_CR6.1","unstructured":"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);"},{"key":"#cr-split#-BF01752396_CR6.2","unstructured":"Part 2, IBM Report RC-5908 (March 1976)."},{"key":"BF01752396_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013131, (1975).","DOI":"10.1007\/3-540-07142-3_71"},{"key":"BF01752396_CR8","doi-asserted-by":"crossref","unstructured":"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\u2013158, (October 1976).","DOI":"10.1109\/SFCS.1976.24"},{"key":"BF01752396_CR9","doi-asserted-by":"crossref","unstructured":"J. V. Guttag, E. Horowitz and D. R. Musser, Abstract Data Types and Software Validation. Research Report 76\u201348. Information Sciences Institute, August 1976.","DOI":"10.21236\/ADA029896"},{"key":"BF01752396_CR10","unstructured":"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."},{"key":"BF01752396_CR11","unstructured":"A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"BF01752396_CR12","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The Complexity of Theorem-Proving Procedures, Third Annual ACM Symposium on Theory of Computing, 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"BF01752396_CR13","doi-asserted-by":"crossref","unstructured":"R. Karp, Reducibility among Combinatorial Problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, 85\u2013104, (1972).","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"BF01752396_CR14","doi-asserted-by":"crossref","unstructured":"R. Ladner, N. A. Lynch and A. L. Selman, Comparison of Polynomial-Time Reducibilities, Sixth Annual ACM Symposium on Theory of Computing, 110\u2013121, 1974.","DOI":"10.1145\/800119.803891"},{"key":"BF01752396_CR15","doi-asserted-by":"crossref","unstructured":"E. K. Blum and D. R. Estes, A Generalization of the Homomorphism Concept, Algebra Universalis, July, 1977.","DOI":"10.1007\/BF02485424"},{"key":"BF01752396_CR16","doi-asserted-by":"crossref","unstructured":"N. A. Lynch, Straight-Line Program Length as a Parameter for Complexity Measures. Tenth Annual ACM Symposium on Theory of Computing, 1978.","DOI":"10.1145\/800133.804343"},{"key":"BF01752396_CR17","unstructured":"N. A. Lynch, Straight-Line Program as a Parameter for Complexity Analysis, to appear in Theoretical Computer Science."},{"key":"BF01752396_CR18","doi-asserted-by":"crossref","unstructured":"N. A. Lynch and E. K. Blum, A Difference in Expressive Power Between Flowcharts and Recursion Schemes, Math. Syst. Theory, 205\u2013211, 1979.","DOI":"10.1007\/BF01776573"},{"key":"BF01752396_CR19","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01744295","volume":"13","author":"N. A. Lynch","year":"1980","unstructured":"N. A. Lynch and E. K. Blum, Relative Complexity of Operation Sets for Numeric and Bit String Algebras, Math. Syst. Theory 13, 187\u2013207 (1980).","journal-title":"Math. Syst. Theory"},{"key":"BF01752396_CR20","doi-asserted-by":"crossref","unstructured":"N. A. Lynch and E. K. Blum, Efficient Reducibility Between Programming Systems, Proceedings of Ninth Annual Symposium on Theory of Computation, 1977.","DOI":"10.1145\/800105.803413"},{"key":"BF01752396_CR21","unstructured":"A. Cremers and T. Hibbard, Formal Modelling of Virtual Machines. To appear in IEEE Transactions on Software Engineering."},{"key":"BF01752396_CR22","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/321978.321990"},{"key":"BF01752396_CR23","unstructured":"R. Rivest, L. Adleman, and M. Dertouzos, On Data Banks and Privacy Homomorphisms, in Foundations of Secure Computation, Academic Press, Inc., 171\u2013179, 1978."},{"key":"BF01752396_CR24","doi-asserted-by":"crossref","unstructured":"A. Chandra, Efficient Compilation of Linear Recursive Programs, Stanford Artificial Intelligence Project MEMO AIM-167, April 1972.","DOI":"10.1109\/SWAT.1973.7"},{"key":"BF01752396_CR25","unstructured":"D. Kfoury, Comparing Algebraic Structures up to Algorithmic Equivalence. In Automata, Languages and Programming, Ed. M. Nivat, North-Holland\/Elsevier, 253\u2013263, 1973."},{"key":"BF01752396_CR26","unstructured":"M. S. Paterson and C. E. Hewitt, Comparative Schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation 119\u2013128, (1970)."},{"key":"BF01752396_CR27","unstructured":"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."},{"key":"BF01752396_CR28","unstructured":"H. R. Strong and S. A. Walker, Characterization of Flowchartable Recursions in Fourth Annual ACM Symposium on Theory of Computing, May 1972."},{"key":"BF01752396_CR29","unstructured":"H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967."},{"key":"BF01752396_CR30","doi-asserted-by":"crossref","unstructured":"K. Weihrauch, On the Computational Complexity of Program Schemata, Cornell University Department of Computer Science, TR 74\u2013196, February 1974.","DOI":"10.1007\/978-3-662-21545-6_24"},{"key":"BF01752396_CR31","unstructured":"D. Knuth, The Art of Computer Programming, 2, Fundamental Algorithms, Addison-Wesley, 1968."},{"key":"BF01752396_CR32","unstructured":"A. Sch\u00f6nhage, Real-Time Simulation of Multi-Dimensional Turing Machines by Storage, Modification Machines, Project MAC Technical Memorandum 7, MIT (1973)."},{"key":"BF01752396_CR33","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan, Reference Machines Require Non-Linear Time to Maintain Disjoint Sets, in 9th Annual ACM Symposium on Theory of Computing, May 1977.","DOI":"10.1145\/800105.803392"},{"key":"BF01752396_CR34","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF00288886","volume":"9","author":"A. L. Rosenberg","year":"1978","unstructured":"A. L. Rosenberg, Data Encodings and Their Costs, Acta Inform. 9, 273\u2013292, (1978).","journal-title":"Acta Inform."},{"key":"BF01752396_CR35","unstructured":"G. Gr\u00e4tzer, Universal Algebra, Van Nostrand, 1968."},{"key":"BF01752396_CR36","unstructured":"P. Cohn, Universal Algebra, Harper and Row, 1965."},{"key":"BF01752396_CR37","unstructured":"A. Borodin, L. J. Guibas, N. A. Lynch and A. C. Yao, Efficient Searching via Partial Ordering, submitted for publication."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01752396.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01752396\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01752396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T18:57:16Z","timestamp":1586285836000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01752396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,12]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1981,12]]}},"alternative-id":["BF01752396"],"URL":"http:\/\/dx.doi.org\/10.1007\/bf01752396","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":["Computational Theory and Mathematics","General Mathematics","Theoretical Computer Science","Computational Theory and Mathematics","Theoretical Computer Science"],"published":{"date-parts":[[1981,12]]}}}