{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T19:10:18Z","timestamp":1735758618556,"version":"3.32.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1984,12,1]],"date-time":"1984-12-01T00:00:00Z","timestamp":470707200000},"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":[[1984,12]]},"DOI":"10.1007\/bf01744435","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T01:31:02Z","timestamp":1118885462000},"page":"85-96","source":"Crossref","is-referenced-by-count":4,"title":["A note on the complexity of program evaluation"],"prefix":"10.1007","volume":"17","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[]},{"given":"Brian S.","family":"Leininger","sequence":"additional","affiliation":[]},{"given":"Louis E.","family":"Rosier","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01744435_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"Aho, A. V., Hopcroft, J. E. and Ullman, J. D.,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"BF01744435_CR2","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1137\/0205045","volume":"5","author":"J. Cherniavsky","year":"1976","unstructured":"Cherniavsky, J., Simple programs realize exactly Presburger formulas,SIAM J. Comput., 5 (1976), pp. 666\u2013677.","journal-title":"SIAM J. Comput."},{"key":"BF01744435_CR3","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/321707.321721","volume":"19","author":"R. Constable","year":"1972","unstructured":"Constable, R. and Borodin, A., Subrecursive programming languages. Part I: Efficiency and program structure,JACM 19 (1972), 526\u2013568.","journal-title":"JACM"},{"key":"BF01744435_CR4","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1145\/322261.322270","volume":"28","author":"E. M. Gurari","year":"1981","unstructured":"Gurari, E. M. and Ibarra, O. H., The complexity of the equivalence problem for simple programs,JACM 28 (1981), 535\u2013560.","journal-title":"JACM"},{"key":"BF01744435_CR5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J. and Stearns, R. E., On the computational complexity of algorithms,Trans. AMS 117 (1965), 285\u2013306.","journal-title":"Trans. AMS"},{"key":"BF01744435_CR6","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"Hopcroft, J. E. and Ullman, J. D.,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA, 1979."},{"key":"BF01744435_CR7","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1137\/0209031","volume":"9","author":"H. B. Hunt III","year":"1980","unstructured":"Hunt, H. B. III, Constable, R. L., and Sahni, S., On the computational complexity of program scheme equivalence,SIAM J. Comput. 9 (1980), 396\u2013416.","journal-title":"SIAM J. Comput."},{"key":"BF01744435_CR8","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/322290.322304","volume":"29","author":"H. B. Hunt III","year":"1982","unstructured":"Hunt, H. B. III, On the complexity of flowchart and loop program schemes and programming languages,JACM 29 (1982), 228\u2013249.","journal-title":"JACM"},{"key":"BF01744435_CR9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/0210003","volume":"10","author":"O. H. Ibarra","year":"1981","unstructured":"Ibarra, O. H. and Leininger, B. S., Characterizations of Presburger functions,SICOMP 10 (1981), 22\u201339.","journal-title":"SICOMP"},{"issue":"1","key":"BF01744435_CR10","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0304-3975(83)90085-3","volume":"26","author":"O. H. Ibarra","year":"1983","unstructured":"Ibarra, O. H. and Rosier, L. E., Simple programming languages and restricted classes of Turing machines,Theoretical Computer Science, Vol. 26, No. 1 and 2, pp. 197\u2013220, September 1983.","journal-title":"Theoretical Computer Science"},{"key":"BF01744435_CR11","unstructured":"Ibarra, O. H. and Rosier, L. E., Some comments concerning the analysis of simple programs over different sets of primitives. University of Minnesota, Department of Computer Science, Tech. Rep. No. 82\u201310 (1982)."},{"key":"BF01744435_CR12","doi-asserted-by":"crossref","unstructured":"Kfoury, A. J., Analysis of simple programs over different sets of primitives,7th ACM SIGACT-SIGPLAN Conference Record, 1980, pp. 56\u201361.","DOI":"10.1145\/567446.567452"},{"key":"BF01744435_CR13","volume-title":"The Art of Computer Programming: Vol. 2,Seminumerical Algorithms","author":"D. Knuth","year":"1973","unstructured":"Knuth, D.,The Art of Computer Programming: Vol. 2,Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1973."},{"key":"BF01744435_CR14","volume-title":"An Introduction to the General Theory of Algorithms","author":"M. Machtey","year":"1978","unstructured":"Machtey, M. and Young, P.,An Introduction to the General Theory of Algorithms, North-Holland, New York, NY, 1978."},{"key":"BF01744435_CR15","volume-title":"Weak monadic second order theory of successor is not elementary recursive, Project MAC Report","author":"A. R. Meyer","year":"1972","unstructured":"Meyer, A. R., Weak monadic second order theory of successor is not elementary recursive, Project MAC Report, MIT, Cambridge, MA, 1972."},{"key":"BF01744435_CR16","doi-asserted-by":"crossref","unstructured":"Meyer, A. R. and Ritchie, D. M., The complexity of loop programs,Proc. ACM Nat'l. Conf. (1967), 465\u2013469.","DOI":"10.1145\/800196.806014"},{"key":"BF01744435_CR17","unstructured":"Meyer, A. R. and Stockmeyer, L. J., Nonelementary word problems in automata and logic,Proc. AMS Symp. on Complexity of Computation, 1973."},{"key":"BF01744435_CR18","volume-title":"Computation: Finite and Infinite Machines","author":"M. L. Minsky","year":"1967","unstructured":"Minsky, M. L.,Computation: Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, NJ, 1967."},{"key":"BF01744435_CR19","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L. J. and Meyer, A. R., Word problems requiring exponential space,Proc. Fifth Annual ACM STOC (1973), 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"BF01744435_CR20","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/321607.321621","volume":"17","author":"D. Tsichritzis","year":"1970","unstructured":"Tsichritzis, D., The equivalence problem of simple programs,JACM 17 (1970), 729\u2013738.","journal-title":"JACM"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744435.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01744435\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T18:57:35Z","timestamp":1735757855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01744435"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,12]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1984,12]]}},"alternative-id":["BF01744435"],"URL":"https:\/\/doi.org\/10.1007\/bf01744435","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"type":"print","value":"0025-5661"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[1984,12]]}}}