{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:50Z","timestamp":1725663710407},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[[1994]]},"DOI":"10.1007\/3-540-57785-8_137","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:19:00Z","timestamp":1330244340000},"page":"137-148","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Are parallel machines always faster than sequential machines?"],"prefix":"10.1007","author":[{"given":"Louis","family":"Mak","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"11_CR1","volume-title":"The Design and Analysis of Parallel Algorithms","author":"S. G. Akl","year":"1989","unstructured":"S. G. Akl. The Design and Analysis of Parallel Algorithms. Prentice Hall, Englewood Cliffs, New Jersey, 1989."},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation. J. Assoc. Comput. Mach., 28:114\u2013133, 1981.","journal-title":"J. Assoc. Comput. Mach."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"A. K. Chandra and L. J. Stockmeyer. Alternation. In Proc. 17th Ann. IEEE Symp. on Foundations of Computer Science, pages 98\u2013108, 1976.","DOI":"10.1109\/SFCS.1976.4"},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S. A. Cook","year":"1973","unstructured":"S. A. Cook and R. A. Reckhow. Time bounded random access machines. J. Comput. System Sci., 7:354\u2013375, 1973.","journal-title":"J. Comput. System Sci."},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0022-0000(85)90011-X","volume":"30","author":"P. W. Dymond","year":"1985","unstructured":"P. W. Dymond and M. Tompa. Speedups of deterministic machines by synchronous parallel machines. J. Comput. System Sci., 30:149\u2013161, 1985.","journal-title":"J. Comput. System Sci."},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie. Parallelism in random access machines. In Proc. 10th Ann. ACM Symp. on Theory of Computing, pages 114\u2013118, 1978.","DOI":"10.1145\/800133.804339"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"L. M. Goldschlager","year":"1982","unstructured":"L. M. Goldschlager. A universal interconnection pattern for parallel computers. J. Assoc. Comput. Mach., 29:1073\u20131086, 1982.","journal-title":"J. Assoc. Comput. Mach."},{"key":"11_CR8","first-page":"869","volume-title":"Handbook of Theoretical Computer Science, volume A","author":"R. M. Karp","year":"1990","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, chapter 17, pages 869\u2013941. MIT Press, Cambridge, Massachusetts, 1990."},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0217005","volume":"17","author":"J. Katajainen","year":"1988","unstructured":"J. Katajainen, J. van Leeuwen, and M. Penttonen. Fast simulation of Turing machines by random access machines. SIAM J. Comput., 17:77\u201388, 1988.","journal-title":"SIAM J. Comput."},{"key":"11_CR10","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1145\/8312.8317","volume":"18","author":"I. Parberry","year":"1986","unstructured":"I. Parberry. Parallel speedup of sequential machines: a defense of the parallel computation thesis. ACM SIGACT News, 18:54\u201367, 1986.","journal-title":"ACM SIGACT News"},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0022-0000(88)90030-X","volume":"36","author":"I. Parberry","year":"1988","unstructured":"I. Parberry and G. Schnitger. Parallel computation with threshold functions. J. Comput. System Sci., 36:278\u2013302, 1988.","journal-title":"J. Comput. System Sci."},{"key":"11_CR12","first-page":"391","volume":"14","author":"W. Paul","year":"1980","unstructured":"W. Paul and R. Reischuk. On alternation II. Acta Inform., 14:391\u2013403, 1980.","journal-title":"Acta Inform."},{"key":"11_CR13","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/0022-0000(81)90035-0","volume":"22","author":"W. Paul","year":"1981","unstructured":"W. Paul and R. Reischuk. On time versus space II. J. Comput. System Sci., 22:312\u2013327, 1981.","journal-title":"J. Comput. System Sci."},{"key":"11_CR14","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0213004","volume":"13","author":"J. H. Reif","year":"1984","unstructured":"J. H. Reif. On synchronous parallel computations with independent probabilistic choice. SIAM J. Comput., 13:46\u201356, 1984.","journal-title":"SIAM J. Comput."},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0304-3975(82)90037-8","volume":"19","author":"K. R. Reischuk","year":"1982","unstructured":"K. R. Reischuk. A fast implementation of a multidimensional storage into a tree storage. Theoret. Comput. Sci., 19:253\u2013266, 1982.","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR16","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01786979","volume":"15","author":"W. J. Savitch","year":"1982","unstructured":"W. J. Savitch. Parallel random access machines with powerful instruction sets. Math. Systems Theory, 15:191\u2013210, 1982.","journal-title":"Math. Systems Theory"},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/322108.322119","volume":"26","author":"W. J. Savitch","year":"1979","unstructured":"W. J. Savitch and M. J. Stimson. Time bounded random access machines with parallel processing. J. Assoc. Comput. Mach., 26:103\u2013118, 1979.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:13:34Z","timestamp":1578507214000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_137"}},"subtitle":["Preliminary version"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_137","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}