{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T20:34:40Z","timestamp":1672518880028},"reference-count":21,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"content-version":"tdm","delay-in-days":3864,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["MLQ - Math. Log. Quart."],"published-print":{"date-parts":[[2005,2]]},"DOI":"10.1002\/malq.200410019","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T15:47:00Z","timestamp":1106754420000},"page":"191-200","source":"Crossref","is-referenced-by-count":1,"title":["An unexpected separation result in Linearly Bounded Arithmetic"],"prefix":"10.1002","volume":"51","author":[{"given":"Arnold","family":"Beckmann","sequence":"first","affiliation":[]},{"given":"Jan","family":"Johannsen","sequence":"additional","affiliation":[]}],"member":"311","reference":[{"key":"10.1002\/malq.200410019-BIB1","author":"Ajtai","unstructured":"The complexity of the pigeonhole principle. Combinatorica 14, 417-433 (1994). Preliminary Version in: Proc. 29th Symposium on Foundations of Computer Science, 1988."},{"key":"10.1002\/malq.200410019-BIB2","author":"Alekhnovich","unstructured":"and An exponential separation between regular and general resolution. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 448-456 (2002)."},{"key":"10.1002\/malq.200410019-BIB3","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s00153-002-0169-4","volume":"42","author":"Beckmann","year":"2003","journal-title":"Archive Math. Logic"},{"key":"10.1002\/malq.200410019-BIB4","author":"Beckmann","unstructured":"and Separation results for the size of constant-depth propositional proofs. Submitted 2003."},{"key":"10.1002\/malq.200410019-BIB5","author":"Beckmann","unstructured":"and Bounded Arithmetic and Resolution-Based Proof Systems. Collegium Logicum Vol. 7 (Kurt G\u00f6del Society, Vienna, Austria, 2004). In press."},{"key":"10.1002\/malq.200410019-BIB6","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s000370100000","volume":"10","author":"Bonet","year":"2001","journal-title":"Computational Complexity"},{"key":"10.1002\/malq.200410019-BIB7","author":"Buss","unstructured":"Bounded Arithmetic. Studies in Proof Theory (Bibliopolis, Naples 1986)."},{"key":"10.1002\/malq.200410019-BIB8","author":"Buss","unstructured":"Axiomatizations and conservation results for fragments of bounded arithmetic. In: Logic and Computation (W. Sieg, ed.), Contemporary Mathematics 106, pp. 57-84 (Amer. Math. Soc., Providence 1990)."},{"key":"10.1002\/malq.200410019-BIB9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1112\/plms\/s3-69.1.1","volume":"69","author":"Buss","year":"1994","journal-title":"Proceedings of the London Mathematical Society"},{"key":"10.1002\/malq.200410019-BIB10","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.2307\/2586729","volume":"63","author":"Chiari","year":"1998","journal-title":"J. Symbolic Logic"},{"key":"10.1002\/malq.200410019-BIB11","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1002\/1521-3870(200204)48:3<375::AID-MALQ375>3.0.CO;2-L","volume":"48","author":"Impagliazzo","year":"2002","journal-title":"Math. Logic Quarterly"},{"key":"10.1002\/malq.200410019-BIB12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.2307\/2275250","volume":"59","author":"Kraj\u00ed?ek","year":"1994","journal-title":"J. Symbolic Logic"},{"key":"10.1002\/malq.200410019-BIB13","author":"Kraj\u00ed?ek","unstructured":"Bounded Arithmetic, Propositional Logic, and Complexity Theory (Cambridge University Press, Heidelberg-New York 1995)."},{"key":"10.1002\/malq.200410019-BIB14","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0168-0072(91)90043-L","volume":"52","author":"Kraj\u00ed?ek","year":"1991","journal-title":"Annals Pure Appl. Logic"},{"key":"10.1002\/malq.200410019-BIB15","author":"Kraj\u00ed?ek","unstructured":"and An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures and Algorithms 7, 15 ff. (1995)."},{"key":"10.1002\/malq.200410019-BIB16","author":"Paris","unstructured":"and Counting problems in bounded arithmetic. In: Methods in Mathematical Logic (Caracas, 1983), Lecture Notes in Math. 1130, pp. 317-340 (Springer-Verlag, Berlin 1985)."},{"key":"10.1002\/malq.200410019-BIB17","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"Pitassi","year":"1993","journal-title":"Computational Complexity"},{"key":"10.1002\/malq.200410019-BIB18","author":"Pohlers","unstructured":"Proof Theory: An Introduction. Lecture Notes in Mathematics 1407 (Springer-Verlag, Berlin-Heidelberg-New York 1989)."},{"key":"10.1002\/malq.200410019-BIB19","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0168-0072(99)00008-1","volume":"100","author":"Pollett","year":"1999","journal-title":"Annals Pure Appl. Logic"},{"key":"10.1002\/malq.200410019-BIB20","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1137\/S0097539703428555","volume":"33","author":"Segerlind","year":"2004","journal-title":"SIAM J. Computing"},{"key":"10.1002\/malq.200410019-BIB21","author":"Yao","unstructured":"Separating the polynomial-time hierarchy by oracles. In: Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, pp. 1-10 (1985)."}],"container-title":["MLQ"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200410019","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full\/10.1002\/malq.200410019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,3]],"date-time":"2021-07-03T13:31:55Z","timestamp":1625319115000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200410019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,2]]}},"URL":"https:\/\/doi.org\/10.1002\/malq.200410019","relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,2]]}}}