{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:32Z","timestamp":1725663272095},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_45","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:02:15Z","timestamp":1330203735000},"page":"460-469","source":"Crossref","is-referenced-by-count":5,"title":["On restricted Boolean circuits"],"prefix":"10.1007","author":[{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"45_CR1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/0022-0000(88)90002-5","volume":"37","author":"N. Alon","year":"1988","unstructured":"N. Alon, W. Maass: Meanders and their application in lower bounds arguments, J. Comp. Syst. Sci., 37(1988), 118\u2013129.","journal-title":"J. Comp. Syst. Sci."},{"key":"45_CR2","unstructured":"A. E. Andreev: On a method giving larger than quadratic effective lower bounds for the complexity of \u03c0-schemes, Vestnik Moscow Univ. Ser. 1 (Math. Mech.), 1986, No. 6, 73\u201376. (In Russian.)"},{"key":"45_CR3","unstructured":"L. Babai, P. Pudl\u00e1k, V. R\u00f6dl, E. Szemer\u00e9di: Lower bounds to the complexity of symmetric functions, preprint (1986)."},{"key":"45_CR4","first-page":"129","volume":"166","author":"E. G. Belaga","year":"1984","unstructured":"E. G. Belaga: Locally synchronous complexity in the light of the trans-box method, 1. STACS, LNCS 166(1984), 129\u2013139.","journal-title":"1. STACS, LNCS"},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0304-3975(87)90057-0","volume":"51","author":"E. G. Belaga","year":"1987","unstructured":"E. G. Belaga: Constructive universal algebra: an introduction, Theor. Comp. Sci., 51(1987), 229\u2013238.","journal-title":"Theor. Comp. Sci."},{"key":"45_CR6","unstructured":"E. G. Belaga: Through the mincing machine with a Boolean layer cake, preprint (1987)."},{"key":"45_CR7","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF00276024","volume":"26","author":"E. G. Belaga","year":"1989","unstructured":"E. G. Belaga: Through the mincing machine with a Boolean layer cake. Non-standard computations over Boolean circuits in the lower-bounds-to-circuit-size complexity proving, Acta Inf., 26(1989), 381\u2013407.","journal-title":"Acta Inf."},{"key":"45_CR8","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S. N. Bhatt","year":"1984","unstructured":"S. N. Bhatt, F. T. Leighton: A framework for solving VLSI graph layout problems, J. Comp. Syst. Sci., 28(1984), 300\u2013343.","journal-title":"J. Comp. Syst. Sci."},{"key":"45_CR9","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber, Z. Galil: Explicit construction of linear size superconcentrators, J. Comp. Syst. Sci., 22(1981), 407\u2013420.","journal-title":"J. Comp. Syst. Sci."},{"key":"45_CR10","first-page":"300","volume":"64","author":"L. H. Harper","year":"1977","unstructured":"L. H. Harper: An n log n lower bound on synchronous combinational complexity, Proc. AMS, 64(1977), 300\u2013306.","journal-title":"Proc. AMS"},{"key":"45_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1137\/0208009","volume":"8","author":"L. H. Harper","year":"1979","unstructured":"L. H. Harper, J. E. Savage: Lower bounds on synchronous combinational complexity, SIAM J. Comp., 8(1979), 115\u2013119.","journal-title":"SIAM J. Comp."},{"key":"45_CR12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(87)90194-3","volume":"24","author":"P. Hochschild","year":"1987","unstructured":"P. Hochschild: Multiple cuts, input repetition, and VLSI complexity, Inf. Proc. Lett., 24(1987), 19\u201324.","journal-title":"Inf. Proc. Lett."},{"key":"45_CR13","first-page":"379","volume":"23","author":"Z. M. Kedem","year":"1982","unstructured":"Z. M. Kedem: Optimal allocation of computational resources in VLSI, 23 FOCS (1982), 379\u2013385.","journal-title":"FOCS"},{"key":"45_CR14","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem, A. Zorat: Replication of inputs may save computational resources in VLSI, in: H. T. Kung, R. Sproull, G. Steele (eds.): VLSI Systems and Computations, Comp. Sci. Press (Rockwille, Md.), 1981, 52\u201360.","DOI":"10.1007\/978-3-642-68402-9_7"},{"key":"45_CR15","first-page":"37","volume":"22","author":"Z. M. Kedem","year":"1981","unstructured":"Z. M. Kedem, A. Zorat: On relations between input and communication\/computation in VLSI, 22 FOCS (1981), 37\u201341.","journal-title":"FOCS"},{"key":"45_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton, R. E. Tarjan: A planar separator theorem, SIAM J. Appl. Math., 36(1979), 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"45_CR17","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0209038","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton, R. E. Tarjan: Applications of a planar separator theorem, SIAM J. Comp., 9(1980), 513\u2013524.","journal-title":"SIAM J. Comp."},{"key":"45_CR18","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/3-540-16486-3_103","volume":"223","author":"W. Maass","year":"1986","unstructured":"W. Maass, G. Schnitger: An optimal lower bound for Turing machines with one work tape and a two-way input tape, Structure in Complexity, LNCS 223(1986), 249\u2013264.","journal-title":"Structure in Complexity"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"W. Maass, G. Schnitger, E. Szemer\u00e9di: Two tapes are better than one for off-line Turing machines, 19 STOC (1987), 94\u2013100.","DOI":"10.1145\/28395.28406"},{"key":"45_CR20","first-page":"231","volume":"182","author":"W. F. McColl","year":"1985","unstructured":"W. F. McColl: Planar circuits have short specifications, STACS, LNCS 182 (1985), 231\u2013242.","journal-title":"STACS, LNCS"},{"key":"45_CR21","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0206030","volume":"6","author":"W. J. Paul","year":"1977","unstructured":"W. J. Paul: A 2.5n lower bound on the combinational complexity of Boolean functions, SIAM J. Comp., 6(1977), 427\u2013443.","journal-title":"SIAM J. Comp."},{"key":"45_CR22","doi-asserted-by":"crossref","unstructured":"J. E. Savage: Planar circuit complexity and the performance of VLSI algorithms, in: H. T. Kung, R. Sproull, G. Steele (eds.): VLSI Systems and Computations, Comp. Sci. Press (Rockwille, Md.), 1981, 61\u201367. Also: INRIA Report No. 77 (1981).","DOI":"10.1007\/978-3-642-68402-9_8"},{"key":"45_CR23","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0022-0000(84)90033-3","volume":"29","author":"J. E. Savage","year":"1984","unstructured":"J. E. Savage: The performance of multilective VLSI algorithms, J. Comp. Syst. Sci., 29(1984), 243\u2013272.","journal-title":"J. Comp. Syst. Sci."},{"key":"45_CR24","first-page":"83","volume":"18","author":"A. L. Toom","year":"1967","unstructured":"A. L. Toom: On the complexity of the realization of binary functions having few \u201csubfunctions\u201d, Problems of Cybernetics, 18(1967), 83\u201390. (In Russian.)","journal-title":"Problems of Cybernetics"},{"key":"45_CR25","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(89)90172-5","volume":"30","author":"Gy. Tur\u00e1n","year":"1989","unstructured":"Gy. Tur\u00e1n: Lower bounds for synchronous circuits and planar circuits, Inf. Proc. Lett., 30(1989), 37\u201340.","journal-title":"Inf. Proc. Lett."},{"key":"45_CR26","first-page":"183","volume":"26","author":"D. Uhlig","year":"1973","unstructured":"D. Uhlig: On the relationship between circuit complexity of a Boolean functions and the number of its subfunctions, Problems of Cybernetics, 26(1973), 183\u2013201. (In Russian.)","journal-title":"Problems of Cybernetics"},{"key":"45_CR27","unstructured":"J. D. Ullman: Computational Aspects of VLSI, Comp. Sci. Press (Rockwille, Md.) (1984)."},{"key":"45_CR28","doi-asserted-by":"crossref","unstructured":"I. Wegener: The Complexity of Boolean Functions, Wiley-Teubner Series in Comp. Sci. (1987).","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T13:19:21Z","timestamp":1713619161000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}