{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:32Z","timestamp":1725664412001},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_79","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:33Z","timestamp":1330278573000},"page":"52-76","source":"Crossref","is-referenced-by-count":0,"title":["On parallel hierarchies and R ki"],"prefix":"10.1007","author":[{"given":"Stephen","family":"Bloch","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"issue":"1","key":"4_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(91)90057-S","volume":"53","author":"W. Allen","year":"1991","unstructured":"William Allen. Arithmetizing uniform NC. Annals of Pure and Applied Logic, 53(1):1\u201350, 1991. See also Divide and Conquer as a Foundation of Arithmetic, Ph.D. thesis, University of Hawaii at Manoa, 1988.","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"S. Bellantoni","year":"1992","unstructured":"Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the polytime functions. computational complexity, 2:97\u2013110, Dec 1992.","journal-title":"computational complexity"},{"key":"4_CR3","volume-title":"PhD thesis","author":"S. Bloch","year":"1992","unstructured":"Stephen Bloch. Divide and Conquer in Parallel Complexity and Proof Theory. PhD thesis, University of California, San Diego, 1992."},{"issue":"2","key":"4_CR4","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01202288","volume":"4","author":"S. Bloch","year":"1994","unstructured":"Stephen Bloch. Function-algebraic characterizations of log and polylog parallel time, computational complexity, 4(2):175\u2013205, 1994. See also Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 193\u2013206, 1992.","journal-title":"computational complexity"},{"unstructured":"Stephen Bloch. Parameter-free induction in bounded arithmetic. In preparation for submission, 1995.","key":"4_CR5"},{"key":"4_CR6","volume-title":"Number 3 in Studies in Proof Theory","author":"S. R. Buss","year":"1986","unstructured":"Samuel R. Buss. Bounded Arithmetic. Number 3 in Studies in Proof Theory. Bibliopolis (Naples), 1986."},{"unstructured":"Samuel R. Buss. Axiomatizations and conservation results for theories of bounded arithmetic. In Proceedings of a Workshop in Logic and Computation, AMS Contemporary Mathematics, May 1987.","key":"4_CR7"},{"unstructured":"Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Manuscript, 1994.","key":"4_CR8"},{"doi-asserted-by":"crossref","unstructured":"Samuel R. Buss, Jan Kraj\u00ed\u010dek, and Gaisi Takeuti. Provably total functions in bounded arithmetic theories R 3 i , U 2 i and V 2 i . In P. Clote and J. Kraj\u00ed\u010dek, editors, Arithmetic, Proof Theory and Computational Complexity, pages 116\u2013161. Oxford University Press, 1993.","key":"4_CR9","DOI":"10.1093\/oso\/9780198536901.003.0006"},{"issue":"1","key":"4_CR10","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28(1):114\u2013133, January 1981.","journal-title":"Journal of the ACM"},{"unstructured":"Peter Clote. A first order theory for the parallel complexity class NC. Technical Report BCCS-8901, Boston College, 1989.","key":"4_CR11"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0168-0072(92)90068-B","volume":"56","author":"P. Clote","year":"1992","unstructured":"Peter Clote and Gaisi Takeuti. Bounded arithmetic for NC, ALogTIME, L and NL. Annals of Pure and Applied Logic, 56:73\u2013117, 1992.","journal-title":"Annals of Pure and Applied Logic"},{"unstructured":"A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Logic, Methodology and Philosophy of Science II, pages 24\u201330. North-Holland, 1965.","key":"4_CR13"},{"unstructured":"Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Richard M. Karp, editor, Complexity of Computations, volume 7 of SIAM-AMS Proceedings, pages 43\u201373. 1974.","key":"4_CR14"},{"unstructured":"Jay Hook. A many-sorted approach to predicative mathematics. PhD thesis, Princeton University, 1983.","key":"4_CR15"},{"issue":"2","key":"4_CR16","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1090\/S0002-9947-1993-1124169-X","volume":"338","author":"J. Kraj\u00ed\u010dek","year":"1993","unstructured":"Jan Kraj\u00ed\u010dek. Fragments of bounded arithmetic and bounded query classes. Transactions of the AMS, 338(2):587\u2013598, August 1993.","journal-title":"Transactions of the AMS"},{"doi-asserted-by":"crossref","unstructured":"Jan Kraj\u00ed\u010dek, Pavel Pudl\u00e1k, and Ji\u0159i Sgall. Interactive computations of optimal solutions. In Mathematical Foundations of Computer Science, volume 452 of Lecture Notes in Computer Science, pages 48\u201360. Springer, 1990.","key":"4_CR17","DOI":"10.1007\/BFb0029595"},{"key":"4_CR18","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0168-0072(91)90043-L","volume":"52","author":"J. Kraj\u00ed\u010dek","year":"1991","unstructured":"J. Kraj\u00ed\u010dek, P. Pudl\u00e1k, and G. Takeuti. Bounded arithmetic and the polynomial hierarchy. Annals of Pure and Applied Logic, 52:143\u2013153, 1991.","journal-title":"Annals of Pure and Applied Logic"},{"doi-asserted-by":"crossref","unstructured":"Daniel Leivant. Subrecursion and lambda representation over free algebras. In Samuel Buss and Philip Scott, editors, Feasible Mathematics, Perspectives in Computer Science, pages 281\u2013291. Birkh\u00e4user, 1990.","key":"4_CR19","DOI":"10.1007\/978-1-4612-3466-1_16"},{"doi-asserted-by":"crossref","unstructured":"Edward Nelson. Predicative Arithmetic. Princeton University Press, 1986.","key":"4_CR20","DOI":"10.1515\/9781400858927"},{"key":"4_CR21","doi-asserted-by":"crossref","first-page":"494","DOI":"10.2307\/2269958","volume":"36","author":"R. J. Parikh","year":"1971","unstructured":"Rohit J. Parikh. Existence and feasibility in arithmetic. Journal of Symbolic Logic, 36:494\u2013508, 1971.","journal-title":"Journal of Symbolic Logic"},{"doi-asserted-by":"crossref","unstructured":"Alexander A. Razborov. Bounded arithmetic and lower bounds in Boolean complexity. Manuscript, 1994.","key":"4_CR22","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22:365\u2013383, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR24","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1145\/322047.322060","volume":"25","author":"C.P. Schnorr","year":"1978","unstructured":"C.P. Schnorr. Satisfiability is quasilinear complete in NQL. Journal of the ACM, 25:136\u2013145, 1978.","journal-title":"Journal of the ACM"},{"key":"4_CR25","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. B. Wilson","year":"1985","unstructured":"Christopher B. Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31:169\u2013181, 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR26","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01692056","volume":"20","author":"C. B. Wilson","year":"1987","unstructured":"Christopher B. Wilson. Relativized NC. Math. Systems Theory, 20:13\u201329, 1987.","journal-title":"Math. Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_79.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T16:44:22Z","timestamp":1713631462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_79","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}