{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:34Z","timestamp":1725663094569},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540185352"},{"type":"electronic","value":"9783540480082"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3540185356_27","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:36:46Z","timestamp":1330198606000},"page":"1-25","source":"Crossref","is-referenced-by-count":1,"title":["Lower bound techniques for VLSI algorithms"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Abelson,H.: Lower bounds on information transfer in distributed computations. Proc. 19th Annual IEEE FOCS, IEEE 1978, pp. 151\u2013158.","DOI":"10.1109\/SFCS.1978.22"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Aho,A.V. \u2014 Ullman,J.D. \u2014 Yanakakis,M.: On notions of information transfer in VLSI circuits. Proc. 15th ACM STOC, ACM 1983, pp. 133\u2013139.","DOI":"10.1145\/800061.808742"},{"key":"1_CR3","volume-title":"Closure properties of communication complexity. \u0160VO\u010c 1987, 1, section Theoretical Cybernetics and Mathematical Informatics","author":"M. Ba\u010d\u00edk","year":"1987","unstructured":"Ba\u010d\u00edk, M.: Closure properties of communication complexity. \u0160VO\u010c 1987, 1, section Theoretical Cybernetics and Mathematical Informatics, Comenius University, Bratislava 1987, 12p. (in Slovak)."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Baudet,G.M.: On the area required by VLSI circuits. In: Kung, Sproul, and Steele 1981, pp. 100\u2013107.","DOI":"10.1007\/978-3-642-68402-9_12"},{"issue":"4","key":"1_CR5","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1137\/0211060","volume":"11","author":"R.P. Brent","year":"1982","unstructured":"Brent, R.P. \u2014 Goldschlager, L.M.: Some area time tradeoffs for VLSI. SIAM J. Comput. 11, No.4 (1982), pp. 737\u2013747.","journal-title":"SIAM J. Comput."},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Brent,R.P. \u2014 Kung,H.T.: The chip complexity of binary arithmetic. Proc. 12th Annual ACM STOC, ACM 1980, pp. 190\u2013200.","DOI":"10.1145\/800141.804666"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF00289573","volume":"18","author":"K. Culik II","year":"1983","unstructured":"Culik, K.II. \u2014 Gruska, J. \u2014 Salomaa, A.: Systolic automata for VLSI on balanced trees. Acta Informat. 18 (1983), 335\u2013344.","journal-title":"Acta Informat."},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0304-3975(83)90032-4","volume":"23","author":"K. Culik II","year":"1983","unstructured":"Culik, K.II. \u2014 Gruska, J. \u2014 Salomaa, A.: On a family of L languages resulting from systolic tree automata. Theor. Comp. Sci. 23 (1983), 231\u2013242.","journal-title":"Theor. Comp. Sci."},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"\u010euri\u0161,P. \u2014 Galil,Z. \u2014 Schnitger,G.: Lower bounds on communication complexity. Proc. 15th Annual ACM STOC, ACM 1984, pp. 81\u201391.","DOI":"10.1145\/800057.808668"},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0020-0190(85)90092-4","volume":"21","author":"P. \u010euri\u0161","year":"1985","unstructured":"\u010euri\u0161, P. \u2014 S\u00fdkora, O. \u2014 Vr\u0165o, I. \u2014 Thompson, C.D.: Tight chip lower bounds for discrete Fourier and Walsh-Hadamard transformations. Infor. Proces. Let. 21 (1985), 245\u2013247.","journal-title":"Infor. Proces. Let."},{"key":"1_CR11","series-title":"Lect. Notes in Computer Science","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BFb0030288","volume-title":"Systolic automata \u2014 power, characterizations, nonhomogenity","author":"J. Gruska","year":"1984","unstructured":"Gruska, J.: Systolic automata \u2014 power, characterizations, nonhomogenity. Proc. 11th MFCS '84, Lect. Notes in Computer Science 176, Springer-Verlag, Berlin Heidelberg-New York 1984, pp. 32\u201349."},{"key":"1_CR12","volume-title":"Closure properties of the family of languages defined ba communication complexity. \u0160VO\u010c 1986, 1, section Theoretical Cybernetics and Mathematical Informatics","author":"X. Gub\u00e1\u0161","year":"1986","unstructured":"Gub\u00e1\u0161, X. \u2014 Waczul\u00edk, J.: Closure properties of the family of languages defined ba communication complexity. \u0160VO\u010c 1986, 1, section Theoretical Cybernetics and Mathematical Informatics, Comenius University, Bratislava 1986, 26p. (in Slovak)."},{"key":"1_CR13","volume-title":"Closure properties of the complexity measures A and AT2. \u0160VO\u010c 1987, 1, section VLSI and Computer Graphics","author":"X. Gub\u00e1\u0161","year":"1987","unstructured":"Gub\u00e1\u0161, X. \u2014 Waczul\u00edk, J.: Closure properties of the complexity measures A and AT2. \u0160VO\u010c 1987, 1, section VLSI and Computer Graphics. Comenius University, Bratislava 1987, 25p. (in Slovak)."},{"key":"1_CR14","series-title":"Lect. Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/3-540-13345-3_21","volume-title":"Communication complexity","author":"J. Hromkovi\u010d","year":"1984","unstructured":"Hromkovi\u010d, J.: Communication complexity. Proc. 11th ICALP, Lect. Notes in Computer Science 172, Springer-Verlag, Berlin-Heidelberg-New York 1984, pp. 235\u2013246."},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J.: Relation between Chomsky hierarchy and communication complexity hierarchy. Acta Math. Univ. Com. 47\u201348 (1986).","DOI":"10.1016\/0304-3975(86)90087-3"},{"issue":"5","key":"1_CR16","first-page":"415","volume":"3","author":"J. Hromkovi\u010d","year":"1984","unstructured":"Hromkovi\u010d, J.: Normed protocol and communication complexity. Computers AI 3, No.5 (1984), 415\u2013422.","journal-title":"Computers AI"},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0020-0190(85)90035-3","volume":"21","author":"J. Hromkovi\u010d","year":"1985","unstructured":"Hromkovi\u010d, J.: Linear lower bounds on unbounded fan-in Boolean circuits. Infor. Proces. Let. 21 (1985), 71\u201374.","journal-title":"Infor. Proces. Let."},{"key":"1_CR18","series-title":"Lect. Notes in Computer Science","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/BFb0016268","volume-title":"A new approach to defining the communication complexity for VLSI","author":"J. Hromkovi\u010d","year":"1986","unstructured":"Hromkovi\u010d, J.: A new approach to defining the communication complexity for VLSI. Proc. 12th MFCS '86, Lect. Notes in Computer Science 233, Springer-Verlag, Berlin-Heidelberg-New York 1986, pp. 431\u2013439."},{"key":"1_CR19","unstructured":"Hromkovi\u010d,J. \u2014 Lo\u017ekin,C.A. \u2014 Rybko,A.N. \u2014 Sapo\u017eenko,A.A. \u2014 \u0160kalikova, N.A.: An approach to obtaining lower bounds on space of Boolean circuits. Banach Centre publ., to appear (In Russian)."},{"key":"1_CR20","unstructured":"Hromkovi\u010d,J.: Some complexity aspects of VLSI computations, Part 1.: A framework for the study of information transfer in VLSI circuits. Submitted to Computers AI."},{"key":"1_CR21","unstructured":"Hromkovi\u010d,J.: Some complexity aspects of VLSI computations. Part 2.: Topology of circuits and information transfer. Submitted to Computers AI."},{"key":"1_CR22","unstructured":"Hromkovi\u010d,J.: Some complexity aspects of VLSI computations. Part 5.: Nondeterministic and probabilistic VLSI circuits. Submitted to Computer AI."},{"key":"1_CR23","unstructured":"Hromkovi\u010d,J. \u2014 Pardubsk\u00e1,A.: Some complexity aspects of VLSI computations. Part 3.: On the power of input bit permutation in tree and trellis automata. Submitted to Computers AI."},{"issue":"4","key":"1_CR24","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1137\/0213052","volume":"13","author":"J. Ja 'Ja","year":"1984","unstructured":"Ja 'Ja, J. \u2014 Prasanna Kumar, V.K. \u2014 Simon, J.: Information transfer under different sets of protocols. SIAM J. Comput. 13, No.4 (1984), 840\u2013849.","journal-title":"SIAM J. Comput."},{"key":"1_CR25","volume-title":"Communication complexity","author":"V. Kurcabov\u00e1","year":"1985","unstructured":"Kurcabov\u00e1, V.: Communication complexity. Master thesis, Dept. of Theor. Cybernetics, Comenius University, Bratislava 1985 (in Slovak)."},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Leiserson,C.E.: Area efficient graph algorithms (for VLSI). Proc. 21st Annual IEEE FOCS, IEEE 1980, pp. 270\u2013281.","DOI":"10.1109\/SFCS.1980.13"},{"key":"1_CR27","volume-title":"Area efficient VLSI computations","author":"C.E. Leiserson","year":"1983","unstructured":"Leiserson, C.E.: Area efficient VLSI computations. MIT Press, Cambridge 1983, Mass."},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Lipton,R.J. \u2014 Sedgewick,R.: Lower bounds for VLSI. Proc. 13th Annual ACM STOC, ACM 1981, pp. 300\u2013307.","DOI":"10.1145\/800076.802482"},{"key":"1_CR29","unstructured":"Masek,W.: A fast algorithm for string editing problem and decision graph complexity. M.Sc. thesis, MIT, May 1976."},{"key":"1_CR30","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H. \u2014 Sipser, M.: Communication complexity. J.Comp. Syst. Sci. 28 (1984), 260\u2013269.","journal-title":"J.Comp. Syst. Sci."},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Preparata,F.P.: A mesh-connected area-time optimal VLSI integer multiplier. In: Kung, Sproull, and Steele 1981, pp. 311\u2013316.","DOI":"10.1007\/978-3-642-68402-9_34"},{"issue":"2","key":"1_CR32","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(80)90006-X","volume":"11","author":"F.P. Preparata","year":"1980","unstructured":"Preparata, F.P. \u2014 Vuilemin, J.E.: Area-time optimal VLSI networks for multiplying matrices. Infor. Proces. Let. 11, No.2 (1980), 77\u201380.","journal-title":"Infor. Proces. Let."},{"key":"1_CR33","series-title":"Lect. Notes in Computer Science","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/3-540-10843-2_3","volume-title":"Area-time optimal VLSI networks for computing integer multiplication and discrete Fourier transformation","author":"F.P. Preparata","year":"1981","unstructured":"Preparata, F.P. \u2014 Vuilemin, J.E.: Area-time optimal VLSI networks for computing integer multiplication and discrete Fourier transformation. Proc. 8th ICALP '81, Lect. Notes in Computer Science 115, Springer-Verlag, Berlin-Heidelberg-New York 1981, pp. 29\u201340."},{"key":"1_CR34","unstructured":"Pudl\u00e1k,P.: personal communication."},{"key":"1_CR35","unstructured":"Pudl\u00e1k,P. \u2014 \u017d\u00e1k,S.: Space complexity of computations. Unpublished manuscript, 1982."},{"key":"1_CR36","unstructured":"Salomaa,A.: Systolic tree and trellis automata. Proc. Collq. ACLCS, Gyor 1984."},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Savage,J.E.: Planar circuit complexity and the performance of VLSI algorithms. In: Kung, Sproul, and Steele, 1981, pp. 61\u201367.","DOI":"10.1007\/978-3-642-68402-9_8"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Savage,J.E.: Area-time tradeoffs for mutrix multiplication and related problems in VLSI models. J. Comp. Syst. Sci. 20, No.3, pp. 230\u2013242.","DOI":"10.1016\/0022-0000(81)90029-5"},{"key":"1_CR39","unstructured":"\u0160kalikova,N.A.: On the area complexity of Boolean circuits computing some specific functions. Sbornik rabot po matemati\u010deskoj kibernetike I (1976), Comp. Centre of the Academy of Sciences of USSR, pp. 102\u2013115 (in Russian)."},{"key":"1_CR40","unstructured":"\u0160kalikova,N.A.: On the relation between area and space complexity of Boolean circuits. Metody diskretnogo analiza v ocenkach zlo\u017enosti uprav\u013eaju\u0161\u010dich sistem 38, Novosibirsk 1982, pp. 87\u2013107 (in Russian)."},{"key":"1_CR41","doi-asserted-by":"crossref","unstructured":"Thompson,C.D.: Area-time complexity for VLSI. Proc. 11th Annual ACM STOC, ACM 1979, pp. 81\u201388.","DOI":"10.1145\/800135.804401"},{"key":"1_CR42","volume-title":"A Complexity Theory for VLSI","author":"C.D. Thompson","year":"1980","unstructured":"Thompson, C.D.: A Complexity Theory for VLSI. Doctoral dissertation, CMU-CS-80-140, Computer Sci. Dept., Carnegie \u2014 Mellon University, Pittsburg, August 1980, 131p."},{"key":"1_CR43","unstructured":"Ullman,A.C.: Computational Aspects of VLSI. Computer SCience Press 1984, 495p."},{"key":"1_CR44","doi-asserted-by":"crossref","unstructured":"Yao,A.C.: Some complexity questions related to distributed computing. Proc. 11th Annual ACM STOC, ACM 1979, pp. 209\u2013213.","DOI":"10.1145\/800135.804414"},{"key":"1_CR45","doi-asserted-by":"crossref","unstructured":"Yao,A.C.: The entropic limitations of VLSI computations. Proc. 13th Annual ACM STOC, ACM 1981, pp. 308\u2013311.","DOI":"10.1145\/800076.802483"}],"container-title":["Lecture Notes in Computer Science","Trends, Techniques, and Problems in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3540185356_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:15:05Z","timestamp":1605644105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3540185356_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540185352","9783540480082"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3540185356_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}