{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:27Z","timestamp":1787340807787,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1990,4]]},"abstract":"<jats:p>The prefix problem consits of computing all the products $x_{0}x_{1}\\cdots x_{j}(j = 0,\\cdots, N-1)$, given a sequence ${\\bf x} = (x_{0}, x_{1},\\cdots , x_{N-1})$ of elements in a semigroup. It is shown that there are unbounded fan-in and fan-out Boolean circuits for the prefix problem with constant depth and linear size if and only if the Cayley graph of the semigroup does not contain a special type of cycle called monoidal cycle.<\/jats:p>","DOI":"10.1137\/0219016","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:33:47Z","timestamp":1109226827000},"page":"246-255","source":"Crossref","is-referenced-by-count":9,"title":["Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size"],"prefix":"10.1137","volume":"19","author":[{"given":"G.","family":"Bilardi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675982"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0015730"},{"key":"R3","unstructured":"G. Bilardi, F. P. Preparata,  F.  Makedon,  Digital filtering in VLSI,  Proc. Aegean Workshop on Computing, Loutraki, Greece, Springer-Verlag, Berlin, New York,  1986,  1\u201311 0595.94026"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62052"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, S. Fortune, R. Lipton,  Unbounded fan-in circuits and associative functions,  Proc. 15th Annual ACM Symposium on Theory of Computing, Boston, MA, Association for Computing Machinery, New York,  1983,  52\u201360","DOI":"10.1145\/800061.808732"},{"key":"R6","unstructured":"A. K. Chandra, S. Fortune, R. Lipton,  Lower bounds for constant depth circuits for prefix problems,  Proc. ICALP,  1983"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/007.1"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. Cole, A. Siegel,  On information flow and sorting: New upper and lower bounds for VLSI circuits,  Proc. 26th Annual IEEE Symposium on Foundations of Computer Science, Portland, OR, IEEE Computer Society, Washington, DC,  1985,  208\u2013221","DOI":"10.1109\/SFCS.1985.39"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. Cole, U. Vishkin,  Approximate and exact parallel scheduling with applications to list, tree and graph problems,  Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, Canada, IEEE Computer Society, Washington, DC,  1986,  478\u2013491","DOI":"10.1109\/SFCS.1986.10"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676223"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"D. Dolev, C. Dwork, N. Pippenger, A. Widgerson,  Superconcentrators, generalizers, and generalized connectors with limited depth,  Proc. 15th Annual ACM Symposium on Theory of Computing, Boston, MA, Association for Computing Machinery, New York,  1983,  42\u201351","DOI":"10.1145\/800061.808731"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"F. E. Fitch,  New bounds for parallel prefix circuits,  Proc. 15th Annual ACM Symposium on Theory of Computing, Boston, MA, Association for Computing Machinery, New York,  1983,  100\u2013109","DOI":"10.1145\/800061.808738"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Saxe, M. Sipser,  Parity, circuits, and the polynomial time hierarchy,  Proc. 22nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1981,  260\u2013270","DOI":"10.1109\/SFCS.1981.35"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"J. Hastad,  Almost optimal lower bounds for small depth circuits,  Proc.15th Annual ACM Symposium on Theory of Computing, Berkeley, CA, Association for Computing Machinery, New York,  1986,  6\u201320","DOI":"10.1145\/12130.12132"},{"key":"R15","volume-title":"The Connection Machine","author":"Hillis W. D.","year":"1985"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676201"},{"key":"R17","volume-title":"The Structure of Computers and Computations","author":"Kuck D. J.","year":"1978"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.6312202"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"R20","volume-title":"Counter-free automata","author":"McNaughton Robert","year":"1971"},{"key":"R21","first-page":"589","volume":"7","author":"Ofman Yu.","year":"1963","journal-title":"Soviet Physics Dokl."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0235"},{"key":"R23","unstructured":"N. Pippenger,  1989, private communication"},{"key":"R24","unstructured":"J. Reif,  Probabilistic parallel prefix computation,  Proc. 1984 Internat. Conference on Parallel Processing,  1984,  291\u2013298, August"},{"key":"R25","unstructured":"A. G. Ranade, Ph.D. Thesis,  Fluent Parallel Computation, Department of Computer Science, Yale University,  1989, May"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90003-9"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80041-4"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"A. C. Yao,  Separating the polynomial-time hierarchy by oracles,  Proc. 26th Annual IEEE Symposium on Foundations of Computer Science, Portland, OR, IEEE Computer Society, Washington, DC,  1985,  1\u201310","DOI":"10.1109\/SFCS.1985.49"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Y. Zalcstein,  On star-free events,  Proc. 11th Annual Symposium on Switching and Automata Theory, IEEE, NY,  76\u201380","DOI":"10.1109\/SWAT.1970.14"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0219016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:47Z","timestamp":1787338127000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0219016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,4]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,4]]}},"alternative-id":["10.1137\/0219016"],"URL":"https:\/\/doi.org\/10.1137\/0219016","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,4]]}}}