{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T18:05:11Z","timestamp":1791050711296,"version":"4.1.0"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1988,8]]},"abstract":"<jats:p>A new parallel algorithm is given to evaluate a straight-line program. The algorithm evaluates a program over a commutative semi-ring R of degree d and size n in time $O((\\log n)(\\log nd))$ using $M(n)$ processors, where $M(n)$ is the number of processors required for multiplying $n \\times n$ matrices over the semi-ring R in $O(\\log n)$ time.<\/jats:p>","DOI":"10.1137\/0217044","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:30:13Z","timestamp":1109226613000},"page":"687-695","source":"Crossref","is-referenced-by-count":46,"title":["Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits"],"prefix":"10.1137","volume":"17","author":[{"given":"Gary L.","family":"Miller","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erich","family":"Kaltofen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAHU","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"RAKS","unstructured":"M. Itai, J. Komlos, E. Szemeredi,  An  O(nlogn) sorting network,  Proc. 15th Annual Symposium on the Theory of Computing, ACM, Boston,  1983,  1\u20139, April"},{"key":"RAM","unstructured":"R. Anderson, G. L. Miller,  Optimal parallel algorithm for list ranking, Proe.16th Annual International Conference on Parallel Processing, submitted"},{"key":"RBRE","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"RCOL","doi-asserted-by":"crossref","unstructured":"R. Cole,  Parallel merge sort,  1987, FOC27, IEEE, Toronto, October, pp. 511\u2013516","DOI":"10.1109\/SFCS.1986.41"},{"key":"RCOO","first-page":"99","volume":"27","author":"Cook Stephen A.","year":"1981","journal-title":"Enseign. Math. (2)"},{"key":"RCV","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"RCWA","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, S. Winograd,  Matrix multiplication via arithmetic progressions,  Proc. 19th Annual ACM Symposium on Theory of Computing, ACM, New York,  1987, l\u20136, May","DOI":"10.1145\/28395.28396"},{"key":"RCWB","doi-asserted-by":"publisher","DOI":"10.1137\/0211038"},{"key":"RLAD","doi-asserted-by":"publisher","DOI":"10.1145\/990518.990519"},{"key":"RMAY","doi-asserted-by":"crossref","unstructured":"E. W. Mayr,  The Dynamic Tree Expression Problem, Tech. Report, STAN-CS-87-1156, Stanford University, Department of Computer Science,  1987, May","DOI":"10.21236\/ADA323937"},{"key":"RMR","doi-asserted-by":"crossref","unstructured":"G. L. Miller, J. H. Reif,  Parallel tree contraction and its applications,  Proc. 26th Symposium on Foundations of Computer Science, IEEE, Portland, OR,  1985,  478\u2013489","DOI":"10.1109\/SFCS.1985.43"},{"key":"RMRK","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-16766-8_21"},{"key":"RMT","doi-asserted-by":"crossref","unstructured":"G. L. Miller, S.H. Tend,  Dynamic parallel complexity of computational circuits,  Proc. 19th Annual ACM Symposium on Theory of Computing, ACM, New York,  1987,  254\u2013264, May","DOI":"10.1145\/28395.28423"},{"key":"RREI","doi-asserted-by":"crossref","unstructured":"J. H. Reif,  An optimal parallel algorithm for integer sorting,  Proc. 26th Annual Symposium on Foundations of Computer Science, IEEE, Portland, OR,  1985,  496\u2013504, October","DOI":"10.1109\/SFCS.1985.9"},{"key":"RVIS","doi-asserted-by":"crossref","unstructured":"U. Vishkin,  Randomized speed-ups in parallel computation,  Proc. 16th Annual ACM Symposium on Theory of Computing, ACM, Washington D.C.,  1984,  230\u2013239, April","DOI":"10.1145\/800057.808686"},{"key":"RVS","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10856-4_79"},{"key":"RVSBR","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0217044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:01Z","timestamp":1787337781000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0217044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,8]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,8]]}},"alternative-id":["10.1137\/0217044"],"URL":"https:\/\/doi.org\/10.1137\/0217044","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,8]]}}}