{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:26Z","timestamp":1725663626488},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[[1993]]},"DOI":"10.1007\/3-540-56503-5_39","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T06:15:21Z","timestamp":1330236921000},"page":"386-397","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Limits on the power of parallel random access machines with weak forms of write conflict resolution"],"prefix":"10.1007","author":[{"given":"Faith E.","family":"Fich","sequence":"first","affiliation":[]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[]},{"given":"Bruce","family":"Kapron","sequence":"additional","affiliation":[]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[]},{"given":"Miroslaw","family":"Kutylowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"39_CR1","unstructured":"A. Borodin, J. Hopcroft, M. Paterson, L. Ruzzo, and M. Tompa, \u201cObservations Concerning Synchronous Parallel Models of Computation\u201d, manuscript, 1980."},{"key":"39_CR2","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, \u201cUpper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes\u201d, SIAM J. Comput., volume 15, 1986, pages 87\u201397.","journal-title":"SIAM J. Comput."},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, M. Kuty\u0142owski, and R. Reischuk, \u201cExact Time Bounds for Computing Boolean Functions without Simultaneous Writes\u201d, Proc. Second Annual ACM Symposium on Parallel Algorithms and Architectures, 1990, pages 125\u2013135.","DOI":"10.1145\/97444.97678"},{"key":"39_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D. Eppstein","year":"1988","unstructured":"D. Eppstein and Z. Galil, \u201cParallel Algorithmic Techniques for Combinatorial Computing\u201d, Ann. Rev. Comput. Sci., volume 3, 1988, pages 233\u2013283.","journal-title":"Ann. Rev. Comput. Sci."},{"key":"39_CR5","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/0217037","volume":"17","author":"F. Fich","year":"1988","unstructured":"F. Fich, P. Ragde, and A. Wigderson, \u201cRelations Between Concurrent-Write Models of Parallel Computation\u201d, SIAM J. Comput., volume 17, 1988, pages 606\u2013627.","journal-title":"SIAM J. Comput."},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"P. Fischer, and H. U. Simon, \u201cOn Learning Ring-Sum-Expansions\u201d, Proc. Third Workshop on Computational Learning Theory, 1990, to appear in SIAM J. Comput.","DOI":"10.1016\/B978-1-55860-146-8.50013-8"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie, \u201cParallelism in Random Access Machines\u201d, Proc. 10th Annual Symposium on Theory of Computing, 1978, pages 114\u2013118.","DOI":"10.1145\/800133.804339"},{"key":"39_CR8","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"L. Goldschlager","year":"1982","unstructured":"L. Goldschlager, \u201cA Unified Approach to Models of Synchronous Parallel Machines\u201d, JACM, volume 29, 1982, pages 1073\u20131086.","journal-title":"JACM"},{"issue":"no.1","key":"39_CR9","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0166-218X(90)90082-N","volume":"29","author":"V. Grolmusz","year":"1990","unstructured":"V. Grolmusz and P. Ragde, \u201cIncomparability in Parallel Computation\u201d, Discrete Applied Mathematics, volume 29, no. 1, 1990, pages 63\u201378.","journal-title":"Discrete Applied Mathematics"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"T. Hagerup, \u201cFast and Optimal Simulations between CRCW PRAMs\u201d, Proc. 9th Annual Symposium on Theoretical Aspects of Computer Science, 1992, pages 45\u201348.","DOI":"10.1007\/3-540-55210-3_172"},{"key":"39_CR11","unstructured":"T. Hagerup, personal communication."},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"T. Hagerup and T. Radzik, \u201cEvery Robust CRCW PRAM can Efficiently Simulate a PRIORITY PRAM\u201d, Proc. Second Annual ACM Symposium on Parallel Algorithms and Architectures, 1990, pages 117\u2013124.","DOI":"10.1145\/97444.97677"},{"key":"39_CR13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L. Kucera","year":"1982","unstructured":"L. Kucera, \u201cParallel Computation and Conflicts in Memory Access\u201d, Information Processing Letters, volume 14, 1982, pages 93\u201396.","journal-title":"Information Processing Letters"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"R. Smolensky, \u201cAlgebraic methods in the theory of lower bounds for Boolean circuit complexity\u201d, Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, pages 77\u201382.","DOI":"10.1145\/28395.28404"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:15:32Z","timestamp":1558253732000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"27 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}