{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:25Z","timestamp":1725663265779},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540505174"},{"type":"electronic","value":"9783540460305"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50517-2_77","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:26:01Z","timestamp":1330201561000},"page":"143-153","source":"Crossref","is-referenced-by-count":0,"title":["On parallel sorting and addition with concurrent writes"],"prefix":"10.1007","author":[{"given":"Sanjeev","family":"Saxena","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P. C. P.","family":"Bhatt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. C.","family":"Prasad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"M.Ajtai,J.Komlos and E.Szemeredi, An O(nlog n) Sorting network, Proc 15th ACM Symposium on Theory of Computing (1983), 1\u20139.","DOI":"10.1145\/800061.808726"},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1137\/0216032","volume":"16","author":"Y. Azar","year":"1987","unstructured":"Y. Azar and U. Vishkin, Tight comparison bounds on the complexity of parallel sorting, SIAM J Computing, 16 (1987), 458\u2013464.","journal-title":"SIAM J Computing"},{"key":"11_CR3","first-page":"13","volume":"76","author":"P. Beame","year":"1988","unstructured":"P. Beame, Limits on the power of Concurrent write machines, Info and Contr, 76, (1988) 13\u201328.","journal-title":"Info and Contr"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"P.Beame and J.Hastad(1987), Optimal Bounds for Decision Problems on the CRCW PRAM, Proc 19th annual ACM Symp on theory of Computing, 83\u201393.","DOI":"10.1145\/28395.28405"},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(85)90008-X","volume":"30","author":"A. Borodin","year":"1985","unstructured":"A. Borodin and J.E. Hopcroft, Routing, Merging and Sorting on Parallel Models of Computation, J. Computer System Sc, 30 (1985), 130\u2013145.","journal-title":"J. Computer System Sc"},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A.K. Chandra","year":"1984","unstructured":"A.K. Chandra,L. Stockmeyer and U. Vishkin, Constant Depth Reducibility, SIAM J Computing, 13 (1984), 423\u2013439.","journal-title":"SIAM J Computing"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"R.Cole,Parallel Merge Sort,Proc 27th IEEE Annual Symp on Foundations of computer Science (1986),511\u2013516.","DOI":"10.1109\/SFCS.1986.41"},{"key":"11_CR8","unstructured":"R.Cole and U.Vishkin, Faster Optimal Parallel Prefix Sums and list Ranking, Ultra Computer Note #117 & Computer Sc Tech Rept #227, New York University, Feb 1987."},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. Cook","year":"1986","unstructured":"S. Cook, C. Dwork and R. Reischuk, Upper and lower time bounds for Parallel Random Access Machines without Simultaneous writes, SIAM J Computing, 15 (1986), 87\u201397.","journal-title":"SIAM J Computing"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Hastad J, Almost optimal lower bounds for small depth circuits, Proc 18th ACM Symp Theory of Computing (1986), 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"N.Immerman, Expressibility as a Complexity Measure: Results and Directions, Manuscript, 1987.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"11_CR12","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"C-32","author":"C.P. Kruskal","year":"1983","unstructured":"C.P. Kruskal, Searching, Merging and Sorting in Parallel Computation, IEEE trans Computer, C-32 (1983), 942\u2013946.","journal-title":"IEEE trans Computer"},{"key":"11_CR13","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"C-34","author":"C.P. Kruskal","year":"1985","unstructured":"C.P. Kruskal,L. Rudolph and M. Snir, The power of Parallel Prefix, IEEE trans Computer, C-34 (1985), 965\u2013968.","journal-title":"IEEE trans Computer"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"M.Li and Y.C.Yesha, New lower bounds for parallel computations, Proc 18th ACM Symposium on Theory of Computing (1986),177\u2013187.","DOI":"10.1145\/12130.12148"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"J.F.Rief,An Optimal Algorithm for Integer Sorting,Proc 26th IEEE Annual Symp on Foundations of Computer Sc (1985), 496\u2013504.","DOI":"10.1109\/SFCS.1985.9"},{"key":"11_CR16","unstructured":"S.Saxena,P.C.P.Bhatt and V.C.Prasad, Fastest Possible Parallel Sorting and Addition Algorithms with polynomial number of processors, CSI communications, Dec 1987, 34\u201335."},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"L. Stockmeyer and U. Vishkin, Simulation of Parallel Random Access Machines by Circuits, SIAM J Comput, 13 (1984), 409\u2013422.","journal-title":"SIAM J Comput"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50517-2_77.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T13:03:52Z","timestamp":1713618232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50517-2_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540505174","9783540460305"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-50517-2_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}