{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:24:50Z","timestamp":1742383490523},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,4,1]],"date-time":"1996-04-01T00:00:00Z","timestamp":828316800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,4]]},"DOI":"10.1007\/bf01961540","type":"journal-article","created":{"date-parts":[[2005,7,29]],"date-time":"2005-07-29T16:13:26Z","timestamp":1122653606000},"page":"287-301","source":"Crossref","is-referenced-by-count":9,"title":["Designing checkers for programs that run in parallel"],"prefix":"10.1007","volume":"15","author":[{"given":"R.","family":"Rubinfeld","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01961540_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L., Huang, M., and Kompella, K., Efficient Checkers for Number-Theoretic Computations,Inform. and Comput., to appear.","DOI":"10.1006\/inco.1995.1125"},{"key":"BF01961540_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02122548","volume":"8","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., and Anderson, R., A Random NC Algorithm for Depth First Search,Combinatorica,8 (1988), 1\u201312.","journal-title":"Combinatorica"},{"key":"BF01961540_CR3","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01762120","volume":"3","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Chazelle, B., Guibas, L., O'Dunlaing, C., and Yap, C., Parallel Computational Geometry,Algorithmica,3 (1988), 293\u2013327.","journal-title":"Algorithmica"},{"key":"BF01961540_CR4","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., and Itai, A., Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem,J. Algorithms,7 (1986), 567\u2013583.","journal-title":"J. Algorithms"},{"key":"BF01961540_CR5","doi-asserted-by":"crossref","unstructured":"Amato, N., and Preparata, F., An NC1 Parallel 3D Convex Hull Algorithm,Proc. on Computational Geometry, 1993, pp. 289\u2013297.","DOI":"10.1145\/160985.161152"},{"key":"BF01961540_CR6","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/65950.65958","volume":"36","author":"P. Beame","year":"1989","unstructured":"Beame, P., and Hastad, J., Optimal Bounds for Decision Problems on the CRCW PRAM,J. Assoc. Comput. Mach.,36 (1989), 643\u2013670.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01961540_CR7","doi-asserted-by":"crossref","unstructured":"Blum, M., and Kannan, S., Program Correctness Checking\u22efand the Design of Programs that Check Their Work,Proc. 22nd Symp. on Theory of Computing, 1989, pp. 86\u201397.","DOI":"10.1145\/73007.73015"},{"key":"BF01961540_CR8","doi-asserted-by":"crossref","unstructured":"Blum, M., Luby, M., and Rubinfeld, R., Self-Testing\/Correcting with Applications to Numerical Problems,J. Comput. System Sci.,47(3) (1993).","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"BF01961540_CR9","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/0022-0000(85)90015-7","volume":"30","author":"A. Chandra","year":"1985","unstructured":"Chandra, A., Fortune, S., and Lipton, R., Unbounded Fan-In Circuits and Associative Functions,J. Comput. System Sci.,30 (1985), 222\u2013234.","journal-title":"J. Comput. System Sci."},{"key":"BF01961540_CR10","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"Chandra, A., Stockmeyer, L., and Vishkin, U., Constant Depth Reducibility,SIAM J. Comput.,13 (1984), 423\u2013439.","journal-title":"SIAM J. Comput."},{"key":"BF01961540_CR11","first-page":"32","volume":"70","author":"R. Cole","year":"1986","unstructured":"Cole, R., and Vishkin, U., Faster Optimal Parallel Prefix Sums and List Ranking,Inform. and Comput.,70 (1986), 32\u201353.","journal-title":"Inform. and Comput."},{"key":"BF01961540_CR12","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst, M., Saxe, J., and Sipser, M., Parity, Circuits and the Polynomial Time Hierarchy,Math. Systems Theory,17 (1984), 13\u201328.","journal-title":"Math. Systems Theory"},{"key":"BF01961540_CR13","doi-asserted-by":"crossref","unstructured":"Gazit, H., An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph,Proc. Symp. on Foundations of Computer Science, 1986, pp. 492\u2013501.","DOI":"10.1109\/SFCS.1986.9"},{"key":"BF01961540_CR14","doi-asserted-by":"crossref","unstructured":"Goldberg, M., and Spencer, T., A New Parallel Algorithm for the Maximal Independent Set Problem,Proc. Symp. on Foundations of Computer Science, 1987.","DOI":"10.1109\/SFCS.1987.2"},{"key":"BF01961540_CR15","unstructured":"Gross, M., Irani, S., Rubinfeld, R., and Seidel, R., Personal communication."},{"key":"BF01961540_CR16","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F. T. Leighton","year":"1992","unstructured":"Leighton, F. T.,Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992."},{"key":"BF01961540_CR17","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M., A Simple Parallel Algorithm for the Maximal Independent Set Problem,SIAM J. Comput.,15 (1986), 1036\u20131053.","journal-title":"SIAM J. Comput."},{"key":"BF01961540_CR18","volume-title":"Ph.D. thesis","author":"S. Kannan","year":"1990","unstructured":"Kannan, S., Program Result Checking with Applications, Ph.D. thesis, University of California, Berkeley, CA, 1990."},{"key":"BF01961540_CR19","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02579264","volume":"6","author":"H. Karloff","year":"1986","unstructured":"Karloff, H., A Las Vegas RNC Algorithm for Maximum Matching,Combinatorica,6 (1986), 387\u2013392.","journal-title":"Combinatorica"},{"key":"BF01961540_CR20","unstructured":"Karp, R., and Ramachandran, V., A Survey of Parallel Algorithms for Shared-Memory Machines, Technical Report No. UCB\/CSD 88\/408, University of California, Berkeley, CA."},{"key":"BF01961540_CR21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R. Karp","year":"1986","unstructured":"Karp, R., Upfal, E., and Wigderson, A., Constructing a Perfect Matching is in Random NC,Combinatorica,6 (1986), 35\u201348.","journal-title":"Combinatorica"},{"key":"BF01961540_CR22","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0022-0000(88)90027-X","volume":"36","author":"R. Karp","year":"1988","unstructured":"Karp, R., Upfal, E., and Wigderson, A., The Complexity of Parallel Search,J. Comput. System. Sci.,36 (1988), 225\u2013253.","journal-title":"J. Comput. System. Sci."},{"key":"BF01961540_CR23","doi-asserted-by":"crossref","unstructured":"Matias, Y., and Vishkin, U., Converting High Probability into Nearly-Constant Time \u2014 with Applications to Parallel Hashing,Proc. Symp. on Theory of Computing, 1991, pp. 307\u2013316.","DOI":"10.1145\/103418.103453"},{"key":"BF01961540_CR24","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U., and Vazirani, V., Matching is as Easy as Matrix Inversion,Combinatorica,7 (1987), 105\u2013113.","journal-title":"Combinatorica"},{"key":"BF01961540_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. Preparata","year":"1985","unstructured":"Preparata, F., and Shamos, M.,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"BF01961540_CR26","doi-asserted-by":"crossref","unstructured":"Schieber, B., and Vishkin, U., On Finding Lowest Common Ancestors: Simplification and Parallelization,SIAM J. Comput.,17(6) (1988).","DOI":"10.1137\/0217079"},{"key":"BF01961540_CR27","doi-asserted-by":"crossref","unstructured":"Sch\u00f6nhage, A., and Strassen, V., Schnelle Multiplikation grosser Zahlen,Computing,7, 281\u2013292.","DOI":"10.1007\/BF02242355"},{"key":"BF01961540_CR28","unstructured":"Spivak, M.,Differential Geometry, Vol. 3."},{"key":"BF01961540_CR29","doi-asserted-by":"crossref","unstructured":"Tamassia, R., and Vitter, J. S., Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures,Proc. ACM Symp. on Parallel Algorithms and Architectures, 1989.","DOI":"10.1145\/72935.72978"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01961540.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01961540\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01961540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T12:04:50Z","timestamp":1586347490000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01961540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["BF01961540"],"URL":"https:\/\/doi.org\/10.1007\/bf01961540","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}