{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T17:40:23Z","timestamp":1738258823821,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540694052"},{"type":"electronic","value":"9783540694076"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69407-6_35","type":"book-chapter","created":{"date-parts":[[2008,6,10]],"date-time":"2008-06-10T13:39:35Z","timestamp":1213105175000},"page":"316-325","source":"Crossref","is-referenced-by-count":0,"title":["Many Facets of Complexity in Logic"],"prefix":"10.1007","author":[{"given":"Antonina","family":"Kolokolova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"35_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: $\\Sigma_1^1$ -Formulae on finite structures. Annals of Pure and Applied Logic\u00a024(1), 1\u201348 (1983)","journal-title":"Annals of Pure and Applied Logic"},{"key":"35_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/978-3-540-30201-8_9","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"A. Atserias","year":"2004","unstructured":"Atserias, A., Kolaitis, P.G., Vardi, M.Y.: Constraint propagation as a proof system. In: Wallace, M. (ed.) CP 2004. LNCS, vol.\u00a03258, pp. 77\u201391. Springer, Heidelberg (2004)"},{"key":"35_CR3","unstructured":"Atserias, A.: Fixed-point logics, descriptive complexity and random satisfiability. PhD thesis, UCSC (2002)"},{"key":"35_CR4","unstructured":"Buss, S.: Bounded Arithmetic. Bibliopolis, Naples (1986)"},{"key":"35_CR5","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":"35_CR6","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":"35_CR7","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, pp. 24\u201330. North-Holland, Amsterdam (1965)"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: Feasibly constructive proofs and the propositional calculus. In: Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, pp. 83\u201397 (1975)","DOI":"10.1145\/800116.803756"},{"key":"35_CR9","unstructured":"Cook, S.A.: CSC 2429S: Proof Complexity and Bounded Arithmetic. Course notes (Spring 1998-2002), http:\/\/www.cs.toronto.edu\/~sacook\/csc2429h"},{"key":"35_CR10","unstructured":"Cook, S.: Theories for complexity classes and their propositional translations. In: Krajicek, J. (ed.) Complexity of computations and proofs, pp. 175\u2013227. Quaderni di Matematica (2003)"},{"key":"35_CR11","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. Complexity of computation, SIAM-AMC proceedings\u00a07, 43\u201373 (1974)","journal-title":"Complexity of computation, SIAM-AMC proceedings"},{"key":"35_CR12","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":"35_CR13","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":"35_CR14","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":"35_CR15","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Languages that capture complexity classes. In: 15th ACM STOC symposium, pp. 347\u2013354 (1983)","DOI":"10.1145\/800061.808765"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Immerman: Nondeterministic space is closed under complementation. In: SCT: Annual Conference on Structure in Complexity Theory (1988)","DOI":"10.1109\/SCT.1988.5270"},{"key":"35_CR17","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":"35_CR18","unstructured":"Kolokolova, A.: Systems of bounded arithmetic from descriptive complexity. PhD thesis, University of Toronto (October 2004)"},{"key":"35_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/11538363_26","volume-title":"Computer Science Logic","author":"A. Kolokolova","year":"2005","unstructured":"Kolokolova, A.: Closure properties of weak systems of bounded arithmetic. In: Ong, L. (ed.) CSL 2005. LNCS, vol.\u00a03634, pp. 369\u2013383. Springer, Heidelberg (2005)"},{"key":"35_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511529948","volume-title":"Bounded Arithmetic, Propositional Logic, and Complexity Theory","author":"J. Kraji\u010dek","year":"1995","unstructured":"Kraji\u010dek, J.: Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press, New York (1995)"},{"key":"35_CR21","doi-asserted-by":"publisher","first-page":"494","DOI":"10.2307\/2269958","volume":"36","author":"R. Parikh","year":"1971","unstructured":"Parikh, R.: Existence and feasibility of arithmetic. Journal of Symbolic Logic\u00a036, 494\u2013508 (1971)","journal-title":"Journal of Symbolic Logic"},{"key":"35_CR22","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":"35_CR23","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":"35_CR24","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055, 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR25","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Informatica\u00a026, 279\u2013284 (1988)","journal-title":"Acta Informatica"},{"key":"35_CR26","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)"},{"key":"35_CR27","unstructured":"Trahtenbrot, B.: The impossibility of an algorithm for the decision problem for finite domains. Doklady Academii Nauk SSSR, 70:569\u2013572 (in Russian, 1950)"},{"key":"35_CR28","volume-title":"14th ACM Symp.on Theory of Computing","author":"M.Y. Vardi","year":"1982","unstructured":"Vardi, M.Y.: The complexity of relational query language. In: 14th ACM Symp.on Theory of Computing, Springer, Heidelberg (1982)"},{"issue":"3","key":"35_CR29","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","Logic and Theory of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69407-6_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T17:21:53Z","timestamp":1738257713000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69407-6_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540694052","9783540694076"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69407-6_35","relation":{},"subject":[]}}