{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:31:59Z","timestamp":1725456719285},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540508403"},{"type":"electronic","value":"9783540460985"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/bfb0029012","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:28:19Z","timestamp":1133396899000},"page":"517-529","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Rounds versus time for the two person pebble game"],"prefix":"10.1007","author":[{"given":"Bala","family":"Kalyanasundaram","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,16]]},"reference":[{"key":"44_CR1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0022-0000(85)90011-X","volume":"30","author":"P. Dymond","year":"1985","unstructured":"Dymond P. and Tompa M., Speedups of Deterministic Machines by Synchronous Parallel Machines, J. Comput. Syst. Sci., Vol. 30, 149\u2013161, 1985.","journal-title":"J. Comput. Syst. Sci."},{"key":"44_CR2","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0898-1221(75)90037-1","volume":"1","author":"P. Erdoes","year":"1975","unstructured":"Erdoes P., Graham R.L. and Szemeredi E., On Sparse Graphs with Dense Long Paths, Comp. Math. Appl. 1, 365\u2013369, 1975.","journal-title":"Comp. Math. Appl."},{"key":"44_CR3","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J. Hopcroft","year":"1977","unstructured":"Hopcroft J., Paul W.J., and Valiant L.G., On Time versus Space, J. ACM, Vol 24, 332\u2013337, 1977.","journal-title":"J. ACM"},{"issue":"4","key":"44_CR4","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1145\/322344.322354","volume":"29","author":"T. Lengauer","year":"1982","unstructured":"Lengauer T. and Tarjan R.E., Asymptotically tight Bounds on Time-Space Trade-offs in a Pebble Game, J. ACM, Vol 29, No.4, 1087\u20131130, 1982.","journal-title":"J. ACM"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Paul W.J., Pippenger N., Szemeredi E. and Trotter W.T., On Determinism Versus Non-Determinism and Related Problems, 24th Annual Symposium on Foundations of Computer Science, 429\u2013438, 1983.","DOI":"10.1109\/SFCS.1983.39"},{"key":"44_CR6","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01683275","volume":"10","author":"W.J. Paul","year":"1977","unstructured":"Paul W.J., Tarjan R.E. and Celoni J.R., Space bounds for a game on graphs. Math. Syst. Theory, Vol 10 (1977), 239\u2013251.","journal-title":"Math. Syst. Theory"},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"Pippenger N., Superconcentrators, SIAM Journal of Computing, Vol. 6. No. 2, June 1977.","DOI":"10.1137\/0206022"},{"key":"44_CR8","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/0304-3975(76)90090-6","volume":"2","author":"M.S. Paterson","year":"1976","unstructured":"Paterson M.S., and Valiant L.G., Circuit Size is Nonlinear in Depth, Theoretical Computer Science 2, 397\u2013400, 1976.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"44_CR9","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1214\/aos\/1176346150","volume":"11","author":"J. Rissanen","year":"1983","unstructured":"Rissanen J., A Universal Prio to Integers and Estimation by Minimum Description length, Annals of Statistics, Vol. 11, No. 2, 416\u2013431, 1983.","journal-title":"Annals of Statistics"},{"issue":"3","key":"44_CR10","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W.L. Ruzzo","year":"1977","unstructured":"Ruzzo W.L., On Uniform Circuit Complexity, J. of Comput. Syst. Sci., Vol. 22, No. 3, 365\u2013383, 1977.","journal-title":"J. of Comput. Syst. Sci."},{"key":"44_CR11","doi-asserted-by":"crossref","unstructured":"Schnitger G., On Depth Reduction and Grates, 24th Annual Symposium on Foundations of Computer Science, 323\u2013328, 1983.","DOI":"10.1109\/SFCS.1983.38"},{"key":"44_CR12","unstructured":"Tompa M., A Pebble Game that Models Alternation, Unpublished Manuscript."},{"key":"44_CR13","series-title":"Lecture Notes in Computer Science","first-page":"101","volume-title":"Symposium on Mathematical Foundations of Computer Science","author":"L.G. Valiant","year":"1979","unstructured":"Valiant L.G., Graph-Theoretic Arguments in Low-Level Complexity, Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 67, G. Goos and J. Hartmanis, Eds., Springer-Verlag, New York, 101\u2013112, 1979."},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"Valiant L.G., On nonlinear lower bounds in computational complexity, Proc. 7th Annual ACM Symposium on Theory of Computing, 45\u201353, 1975.","DOI":"10.1145\/800116.803752"}],"container-title":["Lecture Notes in Computer Science","STACS 89"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:23:58Z","timestamp":1578525838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029012"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540508403","9783540460985"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/bfb0029012","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"16 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}