{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T16:10:15Z","timestamp":1736007015424,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540282310"},{"type":"electronic","value":"9783540318972"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11538363_26","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:35:33Z","timestamp":1127828133000},"page":"369-383","source":"Crossref","is-referenced-by-count":1,"title":["Closure Properties of Weak Systems of Bounded Arithmetic"],"prefix":"10.1007","author":[{"given":"Antonina","family":"Kolokolova","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"26_CR1","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.M. Barrington","year":"1990","unstructured":"Barrington, D.M., Immerman, N., Straubing, H.: On uniformity within NC1. Journal of Computer and System Sciences\u00a041(3), 274\u2013306 (1990)","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0168-0072(92)90068-B","volume":"56","author":"P. Clote","year":"1992","unstructured":"Clote, P., Takeuti, G.: Bounded arithmetic for NC, ALOGTIME, L and NL. Annals of Pure and Applied Logic\u00a056, 73\u2013117 (1992)","journal-title":"Annals of Pure and Applied Logic"},{"key":"26_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-2566-9","volume-title":"Feasible Mathematics","author":"P. Clote","year":"1995","unstructured":"Clote, P., Takeuti, G.: First order bounded arithmetic and small boolean circuit complexity classes. In: Feasible Mathematics, vol.\u00a0II, Birkh\u00e4user Inc., Basel (1995)"},{"key":"26_CR4","first-page":"24","volume-title":"Logic, Methodology and Philosophy of Science","author":"A. Cobham","year":"1965","unstructured":"Cobham, A.: The intrinsic computational difficulty of functions. In: Bar-Hillel, Y. (ed.) Logic, Methodology and Philosophy of Science, Amsterdam, pp. 24\u201330. North-Holland, Amsterdam (1965)"},{"key":"26_CR5","unstructured":"Cook, S.: Theories for complexity classes and their propositional translations, pp. 1\u201336 (2004) (submitted)"},{"key":"26_CR6","unstructured":"Cook, S.A.: CSC 2429S: Proof Complexity and Bounded Arithmetic. Course notes (Spring 1998-2002), http:\/\/www.cs.toronto.edu\/~sacook\/csc2429h"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Kolokolova, A.: A second-order system for polynomial-time reasoning based on Gr\u00e4del\u2019s theorem. In: Proceedings of the Sixteens annual IEEE symposium on Logic in Computer Science, pp. 177\u2013186 (2001)","DOI":"10.1109\/LICS.2001.932495"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0168-0072(03)00056-3","volume":"124","author":"S.A. Cook","year":"2003","unstructured":"Cook, S.A., Kolokolova, A.: A second-order system for polytime reasoning based on Gr\u00e4del\u2019s theorem. Annals of Pure and Applied Logic\u00a0124, 193\u2013231 (2003)","journal-title":"Annals of Pure and Applied Logic"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Kolokolova, A.: Bounded arithmetic of NL. In: Proceedings of the Nineteens annual IEEE symposium on Logic in Computer Science, pp. 398\u2013407 (2004)","DOI":"10.1109\/LICS.2004.1319634"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Cook, S., Thapen, N.: The strength of replacement in weak arithmetic. In: Proceedings of the Nineteens annual IEEE symposium on Logic in Computer Science, pp. 256\u2013264 (2004)","DOI":"10.1109\/LICS.2004.1319620"},{"key":"26_CR11","volume-title":"Finite model theory","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite model theory. Springer, Heidelberg (1995)"},{"key":"26_CR12","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Complexity of computation, SIAM-AMC proceedings, vol.\u00a07, pp. 43\u201373 (1974)"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/BFb0020821","volume-title":"STACS 91","author":"E. Gr\u00e4del","year":"1991","unstructured":"Gr\u00e4del, E.: The Expressive Power of Second Order Horn Logic. In: Jantzen, M., Choffrut, C. (eds.) STACS 1991. LNCS, vol.\u00a0480, pp. 466\u2013477. Springer, Heidelberg (1991)"},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E.: Capturing Complexity Classes by Fragments of Second Order Logic. Theoretical Computer Science\u00a0101, 35\u201357 (1992)","journal-title":"Theoretical Computer Science"},{"key":"26_CR15","first-page":"147","volume-title":"14th ACM Symp.on Theory of Computing","author":"N. Immerman","year":"1982","unstructured":"Immerman, N.: Relational queries computable in polytime. In: 14th ACM Symp.on Theory of Computing, pp. 147\u2013152. Springer, Heidelberg (1982)"},{"key":"26_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive complexity. Springer, New York (1999)"},{"key":"26_CR17","unstructured":"Kolokolova, A.: Systems of bounded arithmetic from descriptive complexity. PhD thesis, University of Toronto (October 2004)"},{"key":"26_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004)"},{"key":"26_CR19","unstructured":"Nguyen, P., Cook, S.: Theories for TC0 and other small complexity classes (2004) (submitted)"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ta-Shma, A.: Symmetric logspace is closed under complement. In: Proc. 27th Ann. ACM Symp. on Theory of Computing (STOC 1995), pp. 140\u2013146 (1995)","DOI":"10.1145\/225058.225101"},{"key":"26_CR21","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/oso\/9780198536901.003.0012","volume-title":"Arithmetic, proof theory and computational complexity","author":"A. Razborov","year":"1993","unstructured":"Razborov, A.: An equivalence between second-order bounded domain bounded arithmetic and first-order bounded arithmetic. In: Clote, P., Kraji\u010dek, J. (eds.) Arithmetic, proof theory and computational complexity, pp. 247\u2013277. Clarendon Press, Oxford (1993)"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-Connectivity in Log-Space. Electronic Colloquium on Computational Complexity, ECCC Report TR04-094 (2004)","DOI":"10.1145\/1060590.1060647"},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03, 1\u201322 (1977)","journal-title":"Theoretical Computer Science"},{"key":"26_CR25","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1093\/oso\/9780198536901.003.0016","volume-title":"Arithmetic, proof theory and computational complexity","author":"G. Takeuti","year":"1993","unstructured":"Takeuti, G.: RSUV isomorphism. In: Clote, P., Kraji\u010dek, J. (eds.) Arithmetic, proof theory and computational complexity, pp. 364\u2013386. Clarendon Press, Oxford (1993)"},{"issue":"3","key":"26_CR26","doi-asserted-by":"publisher","first-page":"942","DOI":"10.2307\/2275794","volume":"61","author":"D. Zambella","year":"1996","unstructured":"Zambella, D.: Notes on polynomially bounded arithmetic. The Journal of Symbolic Logic\u00a061(3), 942\u2013966 (1996)","journal-title":"The Journal of Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11538363_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T15:38:41Z","timestamp":1736005121000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11538363_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540282310","9783540318972"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11538363_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}