{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T19:10:07Z","timestamp":1751569807583,"version":"3.41.0"},"reference-count":24,"publisher":"Wiley","issue":"1-2","license":[{"start":{"date-parts":[[2018,4,17]],"date-time":"2018-04-17T00:00:00Z","timestamp":1523923200000},"content-version":"vor","delay-in-days":16,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2018,4]]},"abstract":"Abstract<\/jats:title>The question of whether the bounded arithmetic theoriesandare equal is closely connected to the complexity question of whetheris equal to. In this paper, we examine the still open question of whether the prenex version of,, is equal to. We give new dependent choice\u2010based axiomatizations of the\u2010consequences ofand. Our dependent choice axiomatizations give new normal forms for the\u2010consequences ofand. We use these axiomatizations to give an alternative proof of the finite axiomatizability ofand to show new results such asis finitely axiomatized and that there is a finitely axiomatized theory,, containingand contained in. On the other hand, we show that our theory forsplits into a natural infinite hierarchy of theories. We give a diagonalization result that stems from our attempts to separate the hierarchy for.<\/jats:p>","DOI":"10.1002\/malq.201500092","type":"journal-article","created":{"date-parts":[[2018,4,17]],"date-time":"2018-04-17T17:46:10Z","timestamp":1523987170000},"page":"6-24","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the finite axiomatizability of"],"prefix":"10.1002","volume":"64","author":[{"given":"Chris","family":"Pollett","sequence":"first","affiliation":[{"name":"Department of Computer Science San Jose State University 214 MacQuarrie Hall, 1 Washington Square San Jose CA 95192 United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2018,4,17]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90057-S"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.03.002"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.03.004"},{"volume-title":"Bounded Arithmetic, Studies in Proof Theory Vol. 3","year":"1986","author":"Buss S. R.","key":"e_1_2_7_5_1"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-69.1.1"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511676277"},{"key":"e_1_2_7_8_1","doi-asserted-by":"crossref","unstructured":"P.Clote Polynomial size Frege proofs of certain combinatorial principles in: Arithmetic proof theory and computational complexity.Papers from the conference held in Prague July 2\u20135 1991 edited byP.CloteandJ.Kraj\u00ed\u010dek Oxford Logic Guides Vol. 23 (Oxford University Press 1993) pp.162\u2013184.","DOI":"10.1093\/oso\/9780198536901.003.0007"},{"key":"e_1_2_7_9_1","doi-asserted-by":"crossref","unstructured":"P.CloteandG.Takeuti First\u2010order bounded arithmetic and small boolean circuit complexity classes in: Feasible mathematics. II. Papers from the Second Workshop held at Cornell University Ithaca New York May 28\u201330 1992 edited by P. Clote and J. Remmel Progress in Computer Science and Applied Logic Vol. 13 (Birkh\u00e4user 1995) pp.154\u2013218.","DOI":"10.1007\/978-1-4612-2566-9_6"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(03)00056-3"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1671"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-016-0484-9"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3"},{"volume-title":"Bounded Arithmetic, Propositional Logic, and Complexity Theory, Encyclopedia of Mathematics and its Applications Vol. 60","year":"1995","author":"Kraj\u00ed\u010dek J.","key":"e_1_2_7_14_1"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360106"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200610019"},{"key":"e_1_2_7_18_1","unstructured":"J.Johannsen On sharply bounded length induction in: Computer Science Logic 9th International Workshop CSL '95 Annual Conference of the EACSL Paderborn Germany September 22\u201029 1995 Selected Papers edited by H. K. B\u00fcning Lecture Notes in Computer Science Vol. 1092 (Springer 1996) pp.362\u2013367."},{"issue":"2","key":"e_1_2_7_19_1","first-page":"205","article-title":"A model\u2010theoretic property of sharply bounded formulae","volume":"44","author":"Johannsen J.","year":"1998","journal-title":"with some applications, Math. Log. Q."},{"key":"e_1_2_7_20_1","doi-asserted-by":"crossref","unstructured":"J.JohannsenandC.Pollett On proofs about threshold circuits and counting hierarchies in: Thirteenth Annual IEEE Symposium on Logic in Computer Science Indianapolis Indiana USA June 21\u201024 1998 (IEEE 1998) pp.444\u2013452.","DOI":"10.1109\/LICS.1998.705678"},{"key":"e_1_2_7_21_1","unstructured":"J.JohannsenandC.Pollett On the \u0394b1\u2010bit\u2010comprehension rule in: Logic Colloquium '98 Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic held in Prague Czech Republic August 9\u201015 1998 edited by Sam Buss Petr H\u00e1jek and Pavel Pudl\u00e1k Lecture Notes in Logic Vol. 13 (ASL 2000) pp.262\u2013279."},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2269958"},{"key":"e_1_2_7_23_1","doi-asserted-by":"crossref","unstructured":"C.Pollett A propositional proof system for in: Proof Complexity and Feasible Arithmetics Proceedings of a DIMACS Workshop New Brunswick New Jersey USA April 21\u201024 1996. edited by P. W. Beame and S. R. Buss DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 39 (American Mathematical Society 1998) pp.253\u2013278.","DOI":"10.1090\/dimacs\/039\/14"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00008-1"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(00)00015-4"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201500092","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201500092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T18:54:44Z","timestamp":1751568884000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201500092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["10.1002\/malq.201500092"],"URL":"https:\/\/doi.org\/10.1002\/malq.201500092","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[2018,4]]},"assertion":[{"value":"2015-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}