{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:53:28Z","timestamp":1794336808945,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540616276","type":"print"},{"value":"9783540706366","type":"electronic"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"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":[[1996]]},"DOI":"10.1007\/bfb0024715","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:17:56Z","timestamp":1132366676000},"page":"293-302","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["ERCW PRAMs and optical communication"],"prefix":"10.1007","author":[{"given":"Philip D.","family":"MacKenzie","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"38_CR1","unstructured":"R. J. Anderson and G. L. Miller. Optical communication for pointer based algorithms. Technical Report CRI 88-14, University of Southern California, 1988."},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"R. B. Boppana and M. Sipser. The complexity of finite functions. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, chapter 14, pages 757\u2013804. MIT Press\/Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, L. J. Stockmeyer, and U. Vishkin. A complexity theory for unbounded fan-in parallelism. In Proc. 23th Symp. on Found. of Comp. Sci., pages 1\u201313, 1982.","DOI":"10.1109\/SFCS.1982.3"},{"issue":"1","key":"38_CR4","doi-asserted-by":"publisher","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. Comput., 15(1):87\u201397, February 1986.","journal-title":"SIAM J. Comput."},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"P. Dowd. High performance interprocessor communication through optical wavelength division multiple access channels. In Proc. 18th Symp. on Comp. Arch., pages 96\u2013105, 1991.","DOI":"10.1145\/115953.115963"},{"key":"38_CR6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\u00f6s","year":"1960","unstructured":"P. Erd\u00f6s and R. Rado. Intersection Theorems for Systems of Sets. J. London Math., 35:85\u201390, 1960.","journal-title":"J. London Math."},{"issue":"7","key":"38_CR7","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1109\/12.83620","volume":"40","author":"M. M. Eshaghian","year":"1991","unstructured":"M. M. Eshaghian. Parallel algorithms for image processing on omc. IEEE Trans. Comput., 40(7):827\u2013833, 1991.","journal-title":"IEEE Trans. Comput."},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"F. Fich, R. Impagliazzo, B. Kapron, V. King, and M. Kutylowski. Limits on the power of parallel random access machines with weak forms of write conflict resolution. In Proc. of 10th Symp. on Theor. Aspects of Comp. Sci., page unknown, 1993.","DOI":"10.1007\/3-540-56503-5_39"},{"key":"38_CR9","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/3-540-55706-7_3","volume":"621","author":"F. Fich","year":"1992","unstructured":"F. Fich, M. Kowaluk, M. Kutylowski, K. Lory\u015a, and P. Ragde. Retrieval of scattered information by EREW, CREW, and CRCW PRAMs. In Proc. 3rd Scand. Workshop on Alg. Theory, pages 30\u201341. Lec. Notes in Comp. Sci., Vol. 621, 1992.","journal-title":"Lec. Notes in Comp. Sci."},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"F. E. Fich, F. Meyer auf der Heide, P. Ragde, and A. Wigderson. One, two, three ... infinity: Lower bounds for parallel computation. In Proc. 17th Symp. on Theory of Computing, pages 48\u201358, 1985.","DOI":"10.1145\/22145.22151"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/0217037","volume":"17","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation. SIAM J. Comput., 17:606\u2013627, 1988.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"38_CR12","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0215047","volume":"15","author":"J. Friedman","year":"1986","unstructured":"J. Friedman. Construct O(n log n) size montone formulae for the kth threshold function of n boolean variables. SIAM J. Comput., 15(3):641\u2013654, 1986.","journal-title":"SIAM J. Comput."},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"A. V. Gerbessiotis and L. G. Valiant. Direct bulk-synchronous parallel algorithms. In Proc. Scandinavian Workshop on Algo. Theory, 1992.","DOI":"10.1007\/3-540-55706-7_1"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"M. Ger\u00e9b-Graus and T. Tsantilas. Efficient optical communication in parallel computers. In Proc. ACM Symp. on Para. Alg. and Arch., pages 41\u201348, 1992.","DOI":"10.1145\/140901.140906"},{"key":"38_CR15","unstructured":"P. B. Gibbons, Y. Matias, V. Ramachandran. The Queue-Read Queue-Write PRAM model: Accounting for contention in parallel algorithms. In Proc. ACM-SIAM Symp. on Discrete Algs. 1994, SIAM J Comput, to appear."},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"L. A. Goldberg, M. Jerrum, T. Leighton, and S. Rao. A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer. In Proc. ACM Symp. on Para. Alg. and Arch., pages 300\u2013309, 1993.","DOI":"10.1145\/165231.166108"},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"L. A. Goldberg, M. Jerrum, and P. D. MacKenzie. A lower bound for routing on a completely connected optical communication parallel computer. accepted to SPAA, 1994.","DOI":"10.1145\/165231.166108"},{"key":"38_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0890-5401(87)90062-9","volume":"75","author":"T. Hagerup","year":"1987","unstructured":"T. Hagerup. Towards optimal parallel bucket sorting. Inform. and Comp., 75:39\u201351, 1987.","journal-title":"Inform. and Comp."},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"T. Hagerup and T. Radzik. Every robust CRCW PRAM can efficiently simulate a Priority PRAM. In Proc. 2nd ACM Symp. on Para. Alg. and Arch., pages 117\u2013124, 1990.","DOI":"10.1145\/97444.97677"},{"issue":"1","key":"38_CR20","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2422.322412","volume":"31","author":"H. J. Hoover","year":"1984","unstructured":"H. J. Hoover, M. M. Klawe, and N. J. Pippenger. Bounding fan-out in logical networks. J. Assoc. Comput. Mach., 31(1):13\u201318, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"38_CR21","doi-asserted-by":"crossref","unstructured":"R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, chapter 17, pages 869\u2013941. MIT Press\/Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"issue":"1","key":"38_CR22","first-page":"83","volume":"10","author":"V. M. Khrapchenko","year":"1971","unstructured":"V. M. Khrapchenko. A method for determining lower bounds for the complexity of \u03c0-schemes. Mat. Zametki, 10(1):83\u201392, 1971. (in Russian); English translation in: Math. Notes\n10(1) (1971) 474\u2013479.","journal-title":"Mat. Zametki"},{"issue":"4","key":"38_CR23","first-page":"803","volume":"151","author":"R. E. Krichevskii","year":"1963","unstructured":"R. E. Krichevskii. Complexity of contact circuits realizing a function of logical algebra. Dokl. Akad. Nauk SSSR, 151(4):803\u2013806, 1963. (in Russian); English translation in: Soviet Phys. Dokl.\n8(8) (1964) 770\u2013772.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"38_CR24","volume-title":"ERCW PRAMs and Optical Communication. TR96-16","author":"P. D. MacKenzie","year":"1996","unstructured":"P. D. MacKenzie and V. Ramachandran. ERCW PRAMs and Optical Communication. TR96-16, Dept. of Comp. Sci., Univ of Texas at Austin, 1996."},{"issue":"2","key":"38_CR25","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/321879.321882","volume":"22","author":"D. E. Muller","year":"1975","unstructured":"D. E. Muller and F. P. Preparata. Bounds to complexities of networks for sorting and for switching. J. Assoc. Comput. Mach., 22(2):195\u2013201, April 1975.","journal-title":"J. Assoc. Comput. Mach."},{"key":"38_CR26","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant. Short monotone formulae for the majority function. J. Algorithms, 5:363\u2013366, 1984.","journal-title":"J. Algorithms"},{"key":"38_CR27","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, chapter 18, pages 945\u2013971. MIT Press\/Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50023-0"}],"container-title":["Lecture Notes in Computer Science","Euro-Par'96 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0024715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,19]],"date-time":"2020-04-19T20:33:12Z","timestamp":1587328392000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616276","9783540706366"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0024715","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0024677","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"10 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}