{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:34Z","timestamp":1725664714410},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602491"},{"type":"electronic","value":"9783540447702"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60249-6_68","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:57:49Z","timestamp":1330279069000},"page":"363-373","source":"Crossref","is-referenced-by-count":1,"title":["PRAM's towards realistic parallelism: BRAM's"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Niedermeier","sequence":"first","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A. K. Chandra, and M. Snir. On communication latency in PRAM computations. In Proc. of 1st SPAA, pages 11\u201321, 1989.","key":"31_CR1","DOI":"10.1145\/72935.72937"},{"key":"31_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(90)90188-N","volume":"71","author":"A. Aggarwal","year":"1990","unstructured":"A. Aggarwal, A. K. Chandra, and M. Snir. Communication Complexity of PRAMs. Theoretical Comput. Sci., 71:3\u201328, 1990.","journal-title":"Theoretical Comput. Sci."},{"key":"31_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. Sorting in clog n parallel steps. Combinatorica, 3:1\u201319, 1983.","journal-title":"Combinatorica"},{"unstructured":"A. Chin. Complexity models for all-purpose parallel computation. In Gibbons and Spirakis [8], chapter 14, pages 393\u2013404.","key":"31_CR4"},{"issue":"4","key":"31_CR5","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM J. Comput., 17(4):770\u2013785, Aug. 1988.","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"D. Culler et al. LogP: Towards a realistic model of parallel computation. In 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 1\u201312, May 1993.","key":"31_CR6","DOI":"10.1145\/155332.155333"},{"doi-asserted-by":"crossref","unstructured":"P. W. Dymond and W. L. Ruzzo. Parallel RAMs with owned global memory and deterministic language recognition. In Proc. of 13th ICALP, number 226 in LNCS, pages 95\u2013104. Springer-Verlag, 1986.","key":"31_CR7","DOI":"10.1007\/3-540-16761-7_59"},{"unstructured":"A. Gibbons and P. Spirakis, editors. Lectures on parallel computation. Cambridge International Series on Parallel Computation. Cambridge University Press, 1993.","key":"31_CR8"},{"key":"31_CR9","series-title":"number 487 in LNCS","first-page":"381","volume-title":"Proc. of 2d EDMCC","author":"D. Gomm","year":"1991","unstructured":"D. Gomm, M. Heckner, K.-J. Lange, and G. Riedle. On the design of parallel programs for machines with distributed memory. In A. Bode, editor, Proc. of 2d EDMCC, number 487 in LNCS, pages 381\u2013391, Munich, Federal Republic of Germany, Apr. 1991. Springer-Verlag."},{"issue":"2","key":"31_CR10","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/62.322423","volume":"31","author":"A. Gottlieb","year":"1984","unstructured":"A. Gottlieb and C. P. Kruskal. Complexity results for permuting data and other computations on parallel processors. J. ACM, 31(2):193\u2013209, April 1984.","journal-title":"J. ACM"},{"unstructured":"T. Heywood and C. Leopold. Models of parallelism. Technical Report CSR-28-93, The University of Edinburgh, Department of Computer Science, July 1993.","key":"31_CR11"},{"key":"31_CR12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(90)90192-K","volume":"71","author":"C. P. Kruskal","year":"1990","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. Theoretical Comput. Sci., 71:95\u2013132, 1990.","journal-title":"Theoretical Comput. Sci."},{"key":"31_CR13","series-title":"number 726 in LNCS","first-page":"272","volume-title":"Proc. of 1st ESA","author":"M. Kunde","year":"1993","unstructured":"M. Kunde. Block gossiping on grids and tori: Sorting and routing match the bisection bound deterministically. In T. Lengauer, editor, Proc. of 1st ESA, number 726 in LNCS, pages 272\u2013283, Bad Honnef, Federal Republic of Germany, Sept. 1993. Springer-Verlag."},{"doi-asserted-by":"crossref","unstructured":"M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith. Optimal Average Case Sorting on Arrays. In E. W. Mayr and C. Puech, editors, Proc. of 12th STACS, number 900 in LNCS, pages 503\u2013514. Springer-Verlag, 1995.","key":"31_CR14","DOI":"10.1007\/3-540-59042-0_100"},{"key":"31_CR15","series-title":"number 761 in LNCS","first-page":"104","volume-title":"Proc. of 13th FST&TCS","author":"K.-J. Lange","year":"1993","unstructured":"K.-J. Lange and R. Niedermeier. Data-independences of parallel random access machines. In R. K. Shyamasundar, editor, Proc. of 13th FST&TCS, number 761 in LNCS, pages 104\u2013113, Bombay, India, Dec. 1993. Springer-Verlag."},{"unstructured":"W. F. McColl. General purpose parallel computing. In Gibbons and Spirakis [8], chapter 13, pages 337\u2013391.","key":"31_CR16"},{"key":"31_CR17","series-title":"number 480 in LNCS","first-page":"172","volume-title":"Proc. of 8th STACS","author":"P. Rossmanith","year":"1991","unstructured":"P. Rossmanith. The Owner Concept for PRAMs. In C. Choffrut and M. Jantzen, editors, Proc. of 8th STACS, number 480 in LNCS, pages 172\u2013183, Hamburg, Federal Republic of Germany, Feb. 1991. Springer-Verlag."},{"doi-asserted-by":"crossref","unstructured":"L. G. Valiant. General purpose parallel architectures. In van Leeuwen [20], chapter 18, pages 943\u2013971.","key":"31_CR18","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"doi-asserted-by":"crossref","unstructured":"P. van Emde Boas. Machine models and simulations. In van Leeuwen [20], chapter 1, pages 1\u201366.","key":"31_CR19","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"doi-asserted-by":"crossref","unstructured":"J. van Leeuwen, editor. Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science. Elsevier, 1990.","key":"31_CR20","DOI":"10.1016\/B978-0-444-88071-0.50015-1"},{"doi-asserted-by":"crossref","unstructured":"U. Vishkin. Workshop on \u201cSuggesting computer science agenda(s) for high-performance computing\u201d (Preliminary announcement). Announced via electronic mail on \u201cTheoryNet\u201d, January 1994.","key":"31_CR21","DOI":"10.1145\/197912"},{"issue":"4","key":"31_CR22","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1137\/0217042","volume":"17","author":"P. M. B. Vit\u00e1nyi","year":"1988","unstructured":"P. M. B. Vit\u00e1nyi. Locality, Communication, and Interconnect Length in Multicomputers. SIAM J. Comput., 17(4):659\u2013672, August 1988.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60249-6_68.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:34:20Z","timestamp":1619573660000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60249-6_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602491","9783540447702"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-60249-6_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}