{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T11:53:43Z","timestamp":1757591623000},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194880"},{"type":"electronic","value":"9783540392910"}],"license":[{"start":{"date-parts":[[1988,1,1]],"date-time":"1988-01-01T00:00:00Z","timestamp":567993600000},"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":[[1988]]},"DOI":"10.1007\/3-540-19488-6_126","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:13:17Z","timestamp":1330182797000},"page":"333-346","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A complexity theory of efficient parallel algorithms"],"prefix":"10.1007","author":[{"given":"Clyde P.","family":"Kruskal","sequence":"first","affiliation":[]},{"given":"Larry","family":"Rudolph","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Snir","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and A. K. Chandra, Communication complexity of PRAM's. 15th ICALP (1988).","DOI":"10.1007\/3-540-19488-6_103"},{"key":"24_CR2","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0216053","volume":"16","author":"H. Alt","year":"1987","unstructured":"H. Alt, T. Hagerup, K. Mehlhorn, and F. P. Preparata, Deterministic simulation of idealized parallel computers on more realistic ones. SIAM Journal of Computing 16 (1987) 808\u2013835.","journal-title":"SIAM Journal of Computing"},{"key":"24_CR3","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)."},{"key":"24_CR4","unstructured":"R. J. Anderson and G. L. Miller, Optical communication for pointer based algorithms. Manuscript."},{"key":"24_CR5","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M. Blum","year":"1967","unstructured":"M. Blum, A machine-independent theory of the complexity of recursive functions. JACM 14 (1967) 322\u2013336.","journal-title":"JACM"},{"key":"24_CR6","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. A. Cook","year":"1986","unstructured":"S. A. Cook, C. Dwork, and R. Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM Journal of Computing 15 (1986) 87\u201397.","journal-title":"SIAM Journal of Computing"},{"key":"24_CR7","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"L. Carter","year":"1981","unstructured":"L. Carter and M. Wegman, New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22 (1981) 265\u2013279.","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"P. W. Dymond and W. L. Ruzzo, Parallel random access machines with owned global memory and deterministic context free language recognition. 13th ICALP (1986) 95\u2013104.","DOI":"10.1007\/3-540-16761-7_59"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie, Parallelism in random access machines. 10th ACM STOC (1978) 114\u2013118.","DOI":"10.1145\/800133.804339"},{"key":"24_CR10","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1109\/TC.1983.1676201","volume":"TC-32","author":"A. Gottlieb","year":"1983","unstructured":"A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir, The NYU Ultracomputer \u2014 designing an MIMD parallel machine. IEEE Trans. on Computers TC-32 (1983) 175\u2013189.","journal-title":"IEEE Trans. on Computers"},{"key":"24_CR11","doi-asserted-by":"crossref","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. JACM 31 (1984) 193\u2013209.","journal-title":"JACM"},{"key":"24_CR12","doi-asserted-by":"crossref","unstructured":"L. Goldschlager, A unified approach to models of synchronous parallel machines. 10th ACM STOC (1978), 89\u201394.","DOI":"10.1145\/800133.804336"},{"key":"24_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, Parallel computation and conflicts in memory accesses. IPL 14 (1982) 93\u201396.","journal-title":"IPL"},{"key":"24_CR14","unstructured":"C. P. Kruskal, T. Madej, and L. Rudolph, Parallel prefix on fully connected direct connection machine. ICPP (1986) 278\u2013283."},{"key":"24_CR15","unstructured":"C. P. Kruskal, Algorithms for replace-add based paracomputers. ICPP (1982) 219-223."},{"key":"24_CR16","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"TC-32","author":"C. P. Kruskal","year":"1983","unstructured":"C. P. Kruskal, Searching, merging, and sorting in parallel computation. IEEE Trans. on Computers TC-32 (1983) 942\u2013946.","journal-title":"IEEE Trans. on Computers"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir, Efficient synchronization in multiprocessors with shared memory. 6th PODC (1986) 218\u2013228.","DOI":"10.1145\/10590.10609"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir, A complexity theory of efficient parallel algorithms, Technical Report, IBM T. J. Watson Research Center, 1988.","DOI":"10.1007\/3-540-19488-6_126"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"A. K. Karlin and E. Upfal, Parallel hashing \u2014 an efficient implementation of shared memory. 18th ACM STOC (1986) 160\u2013168.","DOI":"10.1145\/12130.12146"},{"key":"24_CR20","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal, and A. Widgerson, Are search and decision problems computationally equivalent? 17th ACM STOC (1985) 464\u2013475.","DOI":"10.1145\/22145.22197"},{"key":"24_CR21","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"TC-30","author":"G. Lev","year":"1981","unstructured":"G. Lev, N. Pippenger, and L. G. Valiant, A fast parallel algorithm for routing in permutation networks. IEEE Trans. on Computers TC-30 (1981) 93\u2013100.","journal-title":"IEEE Trans. on Computers"},{"key":"24_CR22","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn and U. Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Informatica 21 (1984) 339\u2013374.","journal-title":"Acta Informatica"},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"A. G. Ranade, How to emulate shared memory. 28th FOCS (1987) 185\u2013194.","DOI":"10.1109\/SFCS.1987.32"},{"key":"24_CR24","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J. H. Reif","year":"1985","unstructured":"J. H. Reif, Depth-first search is inherently sequential. IPL 20 (1985) 229\u2013234.","journal-title":"IPL"},{"key":"24_CR25","unstructured":"L. Rudolph, Software structures for ultraparallel computing. Ph.D. Thesis, NYU, 1982."},{"key":"24_CR26","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/357114.357116","volume":"2","author":"J. Schwartz","year":"1980","unstructured":"J. Schwartz, Ultracomputers. ACM TOPLAS 2 (1980) 484\u2013521.","journal-title":"ACM TOPLAS"},{"key":"24_CR27","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1137\/0214051","volume":"14","author":"M. Snir","year":"1985","unstructured":"M. Snir, On parallel searching. SIAM Journal of Computing 14 (1985) 688\u2013708.","journal-title":"SIAM Journal of Computing"},{"key":"24_CR28","unstructured":"M. Snir, Asynchronous parallel computations. Manuscript."},{"key":"24_CR29","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0196-6774(83)90033-0","volume":"4","author":"U. Vishkin","year":"1983","unstructured":"U. Vishkin, Implementation of simultaneous memory address access in models that forbid it. Journal of Algorithms 4 (1983) 45\u201350.","journal-title":"Journal of Algorithms"},{"key":"24_CR30","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1109\/TC.1986.1676783","volume":"TC-35","author":"J. S. Vitter","year":"1986","unstructured":"J. S. Vitter and R. A. Simons, New classes for parallel complexity: a study of unification and other complete problems for P. IEEE Trans. on Computers TC-35 (1986) 403\u2013418.","journal-title":"IEEE Trans. on Computers"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19488-6_126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T21:31:05Z","timestamp":1640899865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_126","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}