{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T05:19:13Z","timestamp":1672723153541},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1989,4]]},"abstract":"\n The prefix problem consists of computing all the products\n x<\/jats:italic>\n 0<\/jats:sub>\n x<\/jats:italic>\n 1<\/jats:sub>\n \u2026\n \n x\n j<\/jats:sub>\n <\/jats:italic>\n (\n j<\/jats:italic>\n = 0, \u2026 ,\n N<\/jats:italic>\n - 1), given a sequence x = (\n x<\/jats:italic>\n 0<\/jats:sub>\n ,\n x<\/jats:italic>\n 1<\/jats:sub>\n , \u2026 ,\n x<\/jats:italic>\n \n N-<\/jats:italic>\n 1\n <\/jats:sub>\n ) of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with Boolean networks, which are synchronized interconnections of Boolean gates and one-bit storage devices. This complexity crucially depends upon two properties of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup), and memory-induciveness (arbitrarily long products of semigroup elements are true functions of all their factors). A nontrivial characterization is given of non-memory-inducive semigroups as those whose recurrent subsemigroup (formed by the elements with self-loops in the Cayley graph) is the direct product of a left-zero semigroup and a right-zero semigroup. Denoting by\n S<\/jats:italic>\n and\n T<\/jats:italic>\n size and computation time, respectively, we have S = \u0398((\n N<\/jats:italic>\n \/\n T<\/jats:italic>\n )log(\n N<\/jats:italic>\n \/\n T<\/jats:italic>\n )) for memory-inducive non-cycle-free semigroups, and S = \u0398(\n N<\/jats:italic>\n \/\n T<\/jats:italic>\n ) for all other semigroups. We have\n T<\/jats:italic>\n \u03b5 [\u03a9(log\n N<\/jats:italic>\n ), \u039f(\n N<\/jats:italic>\n )] for all semigroups, with the exception of those whose recurrent subsemigroup is a right-zero semigroup, for which\n T<\/jats:italic>\n \u03b5 [\u03a9(1), \u039f(\n N<\/jats:italic>\n )]. The preceding results are also extended to the VLSI model of computation. Area-time optimal circuits are obtained for both boundary and nonboundary I\/O protocols.\n <\/jats:p>","DOI":"10.1145\/62044.62052","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"362-382","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Size-time complexity of Boolean networks for prefix computations"],"prefix":"10.1145","volume":"36","author":[{"given":"G.","family":"Bilardi","sequence":"first","affiliation":[{"name":"Cornell Univ., Ithaca, NY"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[{"name":"Univ. of Illinois at Urbana-Champaign, Urbana"}]}],"member":"320","published-online":{"date-parts":[[1989,4]]},"reference":[{"key":"e_1_2_1_1_2","first-page":"100","volume-title":"Computer","author":"BAUDET G. M.","year":"1981","unstructured":"BAUDET , G. M. On the area required by VLSI circuits . In VLSI Systems and Computations, H. T. Kung, R. Sproull, and G. Steele, Eds. Computer Science Press , Rockville, Md ., 1981 , pp. 100 - 107 . BAUDET, G. M. On the area required by VLSI circuits. In VLSI Systems and Computations, H. T. Kung, R. Sproull, and G. Steele, Eds. Computer Science Press, Rockville, Md., 1981, pp. 100-107."},{"key":"e_1_2_1_3_2","first-page":"53","volume-title":"Proceedings of the International Colloquium on Automata","author":"BILARDI G.","year":"1985","unstructured":"BILARDI , G. , AND PREPARATA , F.P. The influence of key length on the area-time complexity of sorting . In Proceedings of the International Colloquium on Automata . Languages, and Programming, W. Brauer, Ed. (Nafplion, Greece, July). Springer-Verlag , New York, 1985 , pp. 53 - 62 . BILARDI, G., AND PREPARATA, F.P. The influence of key length on the area-time complexity of sorting. In Proceedings of the International Colloquium on Automata. Languages, and Programming, W. Brauer, Ed. (Nafplion, Greece, July). Springer-Verlag, New York, 1985, pp. 53-62."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840437"},{"key":"e_1_2_1_5_2","first-page":"1","volume-title":"Proceedings of Aegean Workshop on Computing. F. Makedon, K. Mehlhorn, T. Papathedorou, and P. Spirakis, Eds.","author":"LARDI G.","year":"1986","unstructured":"B} LARDI , G. , AND PREPARATA , F.P. Digital filtering in VLSI . In Proceedings of Aegean Workshop on Computing. F. Makedon, K. Mehlhorn, T. Papathedorou, and P. Spirakis, Eds. ( Loutraki, Greece, July). Springer-Verlag, New York , 1986 , pp. 1 - 11 . B}LARDI, G., AND PREPARATA, F.P. Digital filtering in VLSI. In Proceedings of Aegean Workshop on Computing. F. Makedon, K. Mehlhorn, T. Papathedorou, and P. Spirakis, Eds. (Loutraki, Greece, July). Springer-Verlag, New York, 1986, pp. 1-11."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(80)90034-4","volume":"11","author":"BRENT R. P.","year":"1980","unstructured":"BRENT , R. P. , AND KUNG , H.Y. On the area of binary tree layouts. Inf. Proc. Lett. 11 , 1 ( Aug. 1980 ), 46-48. BRENT, R. P., AND KUNG, H.Y. On the area of binary tree layouts. Inf. Proc. Lett. 11, 1 (Aug. 1980), 46-48.","journal-title":"Inf. Proc. Lett."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/TC.1982.1675982","volume":"3","author":"BRENT R. P.","year":"1982","unstructured":"BRENT , R. P. , AND KUNC , H.T. A regular layout for parallel adders. IEEE Trans. Comput. C-31 , 3 ( Mar. 1982 ), 260 - 264 . BRENT, R. P., AND KUNC, H.T. A regular layout for parallel adders. IEEE Trans. Comput. C-31, 3 (Mar. 1982), 260-264.","journal-title":"IEEE Trans. Comput. C-31"},{"key":"e_1_2_1_8_2","first-page":"52","volume-title":"Proceedings of the 15th Annual Symposium on Theory of Computing","author":"CHANDRA A. K.","year":"1983","unstructured":"CHANDRA , A. K. , FORTUNE , S. , AND LIPTON , R. Unbounded fan-in circuits and associative functions . In Proceedings of the 15th Annual Symposium on Theory of Computing ( Boston, Mass., Apr. 25-27). ACM, New York , 1983 , pp. 52 - 60 . 10.1145\/800061.808732 CHANDRA, A. K., FORTUNE, S., AND LIPTON, R. Unbounded fan-in circuits and associative functions. In Proceedings of the 15th Annual Symposium on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New York, 1983, pp. 52-60. 10.1145\/800061.808732"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BFb0036901","volume-title":"Proceedings of the International Colloquium on Automata, Languages. and Programming","author":"CHANDRA A. K.","year":"1983","unstructured":"CHANDRA , A. K. , FORTUNE , S. , AND LIPTON , R. Lower bounds for constant depth circuits for prefix problems . In Proceedings of the International Colloquium on Automata, Languages. and Programming . Springer-Verlag , New York , 1983 , pp. 109 - 117 . CHANDRA, A. K., FORTUNE, S., AND LIPTON, R. Lower bounds for constant depth circuits for prefix problems. In Proceedings of the International Colloquium on Automata, Languages. and Programming. Springer-Verlag, New York, 1983, pp. 109-117."},{"key":"e_1_2_1_10_2","volume-title":"The Algebraic Theory of Semigroups","author":"CLIFFORD A. H.","year":"1961","unstructured":"CLIFFORD , A. H. , AND PRFSTON , G. B. The Algebraic Theory of Semigroups , vol. I . American Mathematical Society , Providence, R.I. , 1961 . CLIFFORD, A. H., AND PRFSTON, G. B. The Algebraic Theory of Semigroups, vol. I. American Mathematical Society, Providence, R.I., 1961."},{"key":"e_1_2_1_11_2","first-page":"208","volume-title":"Proceedings of the 26th Annual Symposium on the Foundations of Computer Science (Portland, Ore., Oct.). IEEE","author":"COLE R.","year":"1985","unstructured":"COLE , R. , AND SIEGEL , A. On information flow and sorting: New upper and lower bounds for VLSI circuits . In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science (Portland, Ore., Oct.). IEEE , New York , 1985 , pp. 208 - 221 . COLE, R., AND SIEGEL, A. On information flow and sorting: New upper and lower bounds for VLSI circuits. In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science (Portland, Ore., Oct.). IEEE, New York, 1985, pp. 208-221."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48017"},{"key":"e_1_2_1_13_2","first-page":"307","volume":"3","author":"DIZKEL E.","year":"1982","unstructured":"DIZKEL , E. , AND SAHN~ , S. Binary trees and parallel scheduling algorithms. IEEE Trans. Comput. C-32 , 3 ( Mar. 1982 ), 307 - 315 . DIZKEL, E., AND SAHN~, S. Binary trees and parallel scheduling algorithms. IEEE Trans. Comput. C-32, 3 (Mar. 1982), 307-315.","journal-title":"IEEE Trans. Comput. C-32"},{"key":"e_1_2_1_14_2","first-page":"360","volume-title":"Proceedings of the 21st Annual Symposium on the Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE","author":"DVMOND P. W.","year":"1980","unstructured":"DVMOND , P. W. , AND COOK , S.A. Hardware complexity and parallel computation . In Proceedings of the 21st Annual Symposium on the Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE , New York , 1980 , pp. 360 - 372 . DVMOND, P. W., AND COOK, S.A. Hardware complexity and parallel computation. In Proceedings of the 21st Annual Symposium on the Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE, New York, 1980, pp. 360-372."},{"key":"e_1_2_1_15_2","first-page":"I00","volume-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing","author":"FITCH F. E.","year":"1983","unstructured":"FITCH , F. E. New bounds for parallel prefix circuits . In Proceedings of the 15th Annual ACM Symposium on Theory of Computing ( Boston, Mass., Apr. 25-27). ACM, New York , 1983 , pp. I00 - 109 . 10.1145\/800061.808738 FITCH, F. E. New bounds for parallel prefix circuits. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New York, 1983, pp. I00-109. 10.1145\/800061.808738"},{"key":"e_1_2_1_16_2","first-page":"2","volume":"11","author":"JOHNSON R.B.","year":"1980","unstructured":"JOHNSON , R.B. The complexity ofa VLSI adder. Infijr. Process. Lett. 11 , 2 ( Oct. 1980 ), 92-93. JOHNSON, R.B. The complexity ofa VLSI adder. Infijr. Process. Lett. 11, 2 (Oct. 1980), 92-93.","journal-title":"Infijr. Process. Lett."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"10","author":"KRUSKAL C. P.","year":"1985","unstructured":"KRUSKAL , C. P. , RUDOLPH , L. , AND SN 1 R, M . The power of parallel prefix. IEEE Trans. Comput. C-34 , 10 ( Oct. 1985 ), 965 - 968 . KRUSKAL, C. P., RUDOLPH, L., AND SN1R, M. The power of parallel prefix. IEEE Trans. Comput. C-34, 10 (Oct. 1985), 965-968.","journal-title":"IEEE Trans. Comput. C-34"},{"key":"e_1_2_1_18_2","volume-title":"The Structure of Computers and Computations","author":"J.","year":"1978","unstructured":"KucK, D. J. The Structure of Computers and Computations . Wiley , New York , 1978 . KucK, D.J. The Structure of Computers and Computations. Wiley, New York, 1978."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_1_20_2","volume-title":"Counter-Free Automata","author":"MCNAUGHTON R.","year":"1971","unstructured":"MCNAUGHTON , R. , AND PAPERT , S. Counter-Free Automata . M.I.T. Press , Cambridge, Mass ., 1971 . MCNAUGHTON, R., AND PAPERT, S. Counter-Free Automata. M.I.T. Press, Cambridge, Mass., 1971."},{"key":"e_1_2_1_21_2","first-page":"7","volume":"7","author":"OFMAN Yu.","year":"1963","unstructured":"OFMAN , Yu. On the algorithmic complexity of discrete functions. Soy. Phys. Doki. 7 , 7 ( Jan. 1963 ), 589-591. OFMAN, Yu. On the algorithmic complexity of discrete functions. Soy. Phys. Doki. 7, 7 (Jan. 1963), 589-591.","journal-title":"Soy. Phys. Doki."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90003-9"},{"key":"e_1_2_1_24_2","first-page":"308","volume-title":"Proceeding of the 13th Annual ACM Symposium on Theory of Computing (Milwaukee, Wis., May 11-13)","author":"YAO A.","unstructured":"YAO , A. C> The entropic limatation on VLSI computation . In Proceeding of the 13th Annual ACM Symposium on Theory of Computing (Milwaukee, Wis., May 11-13) . ACM, New York, ! 981 , pp. 308 - 311 . 10.1145\/800076.802483 YAO, A.C> The entropic limatation on VLSI computation. In Proceeding of the 13th Annual ACM Symposium on Theory of Computing (Milwaukee, Wis., May 11-13). ACM, New York, ! 981, pp. 308-311. 10.1145\/800076.802483"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/62044.62052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T20:39:38Z","timestamp":1672691978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/62044.62052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,4]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1989,4]]}},"alternative-id":["10.1145\/62044.62052"],"URL":"http:\/\/dx.doi.org\/10.1145\/62044.62052","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1989,4]]},"assertion":[{"value":"1989-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}