{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T20:16:08Z","timestamp":1672690568000},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1983,12,1]],"date-time":"1983-12-01T00:00:00Z","timestamp":439084800000},"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":[[1983,12]]},"DOI":"10.1007\/bf01744566","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T08:56:39Z","timestamp":1118912199000},"page":"9-27","source":"Crossref","is-referenced-by-count":6,"title":["Space-time tradeoffs for linear recursion"],"prefix":"10.1007","volume":"16","author":[{"given":"Sowmitri","family":"Swamy","sequence":"first","affiliation":[]},{"given":"John E.","family":"Savage","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01744566_CR1","unstructured":"Paterson, M. S. and C. E. Hewitt. \u201cComparative Schematology,\u201dProceedings of Proj. MAC Conf. on Concurrent Systems and Parallel Computation, Woods Hole, Massachussets, pp. 119\u2013127, June 2\u20135 (1970)."},{"key":"BF01744566_CR2","doi-asserted-by":"crossref","unstructured":"Chandra, A. K. \u201cEfficient Compilation of Linear Recursive Programs\u201d, IBM Research Rept RC4517, 10 pp. August 29, 1973, and theProceedings of the Fourteenth Annual IEEE Symposium on Switching and Automata Theory, pp. 16\u201325, October 15\u201317, 1973.","DOI":"10.1109\/SWAT.1973.7"},{"issue":"2","key":"BF01744566_CR3","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J. E. Hopcroft","year":"1977","unstructured":"Hopcroft, J. E., W. J. Paul, and L. G. Valiant. \u201cOn Time Versus Space\u201d,JACM, vol. 24, no. 2, pp. 332\u2013337, 1977.","journal-title":"JACM"},{"key":"BF01744566_CR4","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01683275","volume":"10","author":"W. J. Paul","year":"1977","unstructured":"Paul, W. J., R. E. Tarjan, and J. R. Celoni. \u201cSpace Bounds for a Game on Graphs,\u201dMath. Systems Theory, vol. 10, pp. 239\u2013251, 1977.","journal-title":"Math. Systems Theory"},{"issue":"3","key":"BF01744566_CR5","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/322077.322091","volume":"25","author":"N. Pippenger","year":"1978","unstructured":"Pippenger, N. \u201cA Time-Space Tradeoff\u201d,JACM, vol. 25, no. 3, pp. 509\u2013515 (July 1978).","journal-title":"JACM"},{"key":"BF01744566_CR6","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF00289150","volume":"10","author":"W. J. Paul","year":"1978","unstructured":"Paul, W. J. and R. E. Tarjan. \u201cTime-Space Tradeoffs in a Pebble Game\u201d,Acta Informatica, vol. 10, pp. 111\u2013115, 1978.","journal-title":"Acta Informatica"},{"key":"BF01744566_CR7","doi-asserted-by":"crossref","unstructured":"A. Lingus. \u201cA PSPACE-complete Problem Related to a Pebble Game\u201d, pp. 300\u2013321 inAutomata Languages and Programming, (ed. C. Boehm), Lecture Notes in Computer Science. Springer-Verlag, no. 62 (1978).","DOI":"10.1007\/3-540-08860-1_22"},{"key":"BF01744566_CR8","unstructured":"P. van Emde Boas and J. van Leeuwen. \u201cMove Rules and Trade-Offs in the Pebble Game\u201d, Report RUU-CS-78\u20134, Vakgroep Informatica, U. Utrecht, Utrecht, Netherlands (April\/August 1978)."},{"issue":"4","key":"BF01744566_CR9","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1145\/322217.322233","volume":"27","author":"R. Reischuk","year":"1980","unstructured":"Reischuk, R. \u201cImproved Bounds on the Problem of Time-Space Tradeoff in the Pebble Game\u201d,JACM, vol. 27, no. 4, pp. 839\u2013849 (October 1980).","journal-title":"JACM"},{"key":"BF01744566_CR10","doi-asserted-by":"crossref","unstructured":"Lengauer, T. and Tarjan, R. E. \u201cUpper and Lower Bounds on Time-Space Tradeoffs\u201d,Proc. Eleventh Ann. ACM Symp. on Th. Comp., pp. 262\u2013277 (April 1979).","DOI":"10.1145\/800135.804420"},{"key":"BF01744566_CR11","doi-asserted-by":"crossref","unstructured":"D. Carlson and J. E. Savage. \u201cGraph Pebbling with Many Free Pebbles Can be Difficult\u201d,Proc. 12th Ann. ACM Symp. on Th. Computing, pp. 326\u2013332, April 28\u201330, 1980.","DOI":"10.1145\/800141.804681"},{"key":"BF01744566_CR12","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1109\/TIT.1978.1055938","volume":"24","author":"J. E. Savage","year":"1978","unstructured":"Savage, J. E. and S. Swamy. \u201cSpace-Time Tradeoffs on the FFT Algorithm\u201d,IEEE Transactions on Information Theory, vol. 24, pp. 563\u2013568 (September 1978).","journal-title":"IEEE Transactions on Information Theory"},{"key":"BF01744566_CR13","first-page":"35","volume":"60","author":"D. Yu. Grigoryev","year":"1976","unstructured":"Grigoryev, D. Yu. \u201cAn Application of Separability and Independence Notions for Proving Lower Bounds of Circuit Complexity\u201d,Notes of Scientific Seminars, Steklov Math. Inst., Leningrad Branch, vol. 60, pp. 35\u201348 (1976).","journal-title":"Notes of Scientific Seminars, Steklov Math. Inst., Leningrad Branch"},{"key":"BF01744566_CR14","doi-asserted-by":"crossref","unstructured":"Tompa, M. \u201cTime-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits\u201d,Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 196\u2013204, May 1\u20133, 1978.","DOI":"10.1145\/800133.804348"},{"key":"BF01744566_CR15","doi-asserted-by":"crossref","unstructured":"J. E. Savage and S. Swamy. \u201cSpace-Time Tradeoffs for Oblivious Integer Multiplication\u201d, pp. 498\u2013504 inLecture Notes in Computer Science (ed. H. A. Maurer), Springer-Verlag, vol. 71 (1979).","DOI":"10.1007\/3-540-09510-1_40"},{"key":"BF01744566_CR16","volume-title":"Information Theory and Reliable Communications","author":"R. G. Gallager","year":"1968","unstructured":"Gallager, R. G.Information Theory and Reliable Communications. New York: John Wiley and Sons, 1968."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744566.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01744566\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744566","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T15:00:34Z","timestamp":1557327634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01744566"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["BF01744566"],"URL":"https:\/\/doi.org\/10.1007\/bf01744566","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,12]]}}}