{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T00:37:15Z","timestamp":1787359035834,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_102","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:45:44Z","timestamp":1330195544000},"page":"234-248","source":"Crossref","is-referenced-by-count":3,"title":["A depth-size tradeoff for boolean circuits with unbounded fan-in"],"prefix":"10.1007","author":[{"given":"James F.","family":"Lynch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, \u2211 1 1 -formulae on finite structures, Ann. Applied and Pure Logic 24 (1983), 1\u201348.","journal-title":"Ann. Applied and Pure Logic"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"T. Baker, J. Gill, and R. Solovay, Relativizations of the P-?NP Question, SIAM J. Comp. (1975), 431\u2013442.","DOI":"10.1137\/0204037"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"A. Chandra, S. Fortune, and R. Lipton, Unbounded fan-in circuits and associative functions, Proc. 15th ACM Symp. on Theory of Comp. (1983), 52\u201360.","DOI":"10.1145\/800061.808732"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"A. Chandra, L. Stockmeyer, and U. Vishkin, A complexity theory for unbounded fan-in parallelism, Proc. 23rd IEEE Symp. on Found. Comp. Sci. (1982), 1\u201313.","DOI":"10.1109\/SFCS.1982.3"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"S. Cook, The complexity of theorem-proving procedures, Proc. Third ACM Symp. on Theory of Comp. (1971), 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"P. Duris, Z. Galil, W. Paul, and R. Reischuk, Two nonlinear lower bounds, Proc. 15th ACM Symp. on Theory of Comp. (1983), 127\u2013132.","DOI":"10.1145\/800061.808741"},{"key":"18_CR7","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, R.M. Karp, ed., AMS, Providence (1974), 43\u201373."},{"key":"18_CR8","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(85)90045-3","volume":"36","author":"R. Fagin","year":"1985","unstructured":"R. Fagin, M. Klawe, N. Pippenger, and L. Stockmeyer, Bounded-depth, polynomial-size circuits for symmetric functions, Theoretical Comp. Sci. 36 (1985), 239\u2013250.","journal-title":"Theoretical Comp. Sci."},{"key":"18_CR9","volume-title":"An Introduction to Probability Theory and its Applications, Vol. I","author":"W. Feller","year":"1968","unstructured":"W. Feller, An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed., Wiley, New York (1968).","edition":"3rd ed."},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, and M. Sipser, Parity, circuits, and the polynomial-time hierarchy, Math. Systems Theory 17 (1984), 13\u201327.","journal-title":"Math. Systems Theory"},{"key":"18_CR11","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1137\/0213025","volume":"13","author":"E. Grandjean","year":"1984","unstructured":"E. Grandjean, The spectra of first-order sentences and computational complexity, SIAM J. Computing 13 (1984), 356\u2013373.","journal-title":"SIAM J. Computing"},{"key":"18_CR12","doi-asserted-by":"crossref","first-page":"183","DOI":"10.2307\/2268617","volume":"19","author":"L. Henkin","year":"1954","unstructured":"L. Henkin, A generalization of the concept of \u03c9-consistency, J. Symbolic Logic 19 (1954), 183\u2013196.","journal-title":"J. Symbolic Logic"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F. Hennie","year":"1965","unstructured":"F. Hennie, One-tape off-line Turing machine computations, Information and Control 8 (1965), 553\u2013578.","journal-title":"Information and Control"},{"key":"18_CR14","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass. (1979)."},{"key":"18_CR15","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N. Immerman","year":"1981","unstructured":"N. Immerman, Number of quantifiers is better than number of tape cells, J. Comp. Sys. Sci. 22 (1981), 384\u2013406.","journal-title":"J. Comp. Sys. Sci."},{"key":"18_CR16","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"\u2014, Upper and lower bounds for first-order expressibility, J. Comp. Sys. Sci. 25 (1982), 76\u201398.","journal-title":"J. Comp. Sys. Sci."},{"key":"18_CR17","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N. Jones","year":"1974","unstructured":"N. Jones and A. Selman, Turing machines and the spectra of first-order formulas with equality, J. Symbolic Logic 39 (1974), 139\u2013150.","journal-title":"J. Symbolic Logic"},{"key":"18_CR18","first-page":"96","volume-title":"Stud. in Model Theory, MAA Studies in Math., Vol. 8","author":"H. Keisler","year":"1973","unstructured":"H. Keisler, Forcing and the Omitting Types Theorem, Stud. in Model Theory, MAA Studies in Math., Vol. 8, MAA, Buffalo (1973), 96\u2013133."},{"key":"18_CR19","unstructured":"K. Kuratowski, Topology, Academic Press (1966)."},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J. Lynch","year":"1982","unstructured":"J. Lynch, Complexity classes and theories of finite models, Math. Systems Theory 15 (1982), 127\u2013144.","journal-title":"Math. Systems Theory"},{"key":"18_CR21","doi-asserted-by":"crossref","first-page":"246","DOI":"10.2307\/2269096","volume":"21","author":"S. Orey","year":"1956","unstructured":"S. Orey, On \u03c9-consistency and related properties, J. Symbolic Logic 21 (1956), 246\u2013252.","journal-title":"J. Symbolic Logic"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"M. Sipser, Borel sets and circuit complexity, Proc. 15th ACM Symp. on Theory of Comp. (1983), 61\u201369.","DOI":"10.1145\/800061.808733"},{"key":"18_CR23","unstructured":"\u2014, A topological view of some problems in complexity theory, to appear."},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"A. Yao, Separating the polynomial-time hierarchy by cracles, Proc. 26th IEEE Symp. on Found. Comp. Sci. (1985), 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_102.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:10:27Z","timestamp":1605643827000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_102","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}