{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:47Z","timestamp":1760202647691,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":92,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_81","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:50Z","timestamp":1330278590000},"page":"98-130","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Computation models and function algebras"],"prefix":"10.1007","author":[{"given":"Peter","family":"Clote","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/BF01459088","volume":"99","author":"W. Ackermann","year":"1928","unstructured":"W. Ackermann. Zum Hilbertschen Aufbau der reelen Zahlen. Mathematische Annalen, 99:118\u2013133, 1928.","journal-title":"Mathematische Annalen"},{"issue":"1","key":"6_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(91)90057-S","volume":"53","author":"B. Allen","year":"1991","unstructured":"B. Allen. Arithmetizing uniform NC. Annals of Pure and Applied Logic, 53(1):1\u201350, 1991.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"3","key":"6_CR3","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. M. Barrington","year":"1990","unstructured":"D. Mix Barrington, N. Immerman, and H. Straubing. On uniformity in NC 1. Journal of Computer and System Science, 41(3):274\u2013306, 1990.","journal-title":"Journal of Computer and System Science"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"D.A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. Journal of Computer and System Sciences, 38:150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR5","unstructured":"S. Bellantoni. Predicative recursion and computational complexity. Technical Report 264\/92, University of Toronto, Computer Science Department, September 1992. 164 pages."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"S. Bellantoni. Predicative recursion and the polytime hierarchy. In P. Clote and J. Remmel, editors, Feasible Mathematics II, pages 15\u201329. Birkh\u00e4user, 1995.","DOI":"10.1007\/978-1-4612-2566-9_2"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"S. Bellantoni","year":"1992","unstructured":"S. Bellantoni and S. Cook. A new recursion-theoretic characterization of the polytime functions. Computational Complexity, 2:97\u2013110, 1992.","journal-title":"Computational Complexity"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"2280","DOI":"10.1007\/BF01629435","volume":"20","author":"A. Bel'tyukov","year":"1982","unstructured":"A. Bel'tyukov. A computer description and a hierarchy of initial Grzegorczyk classes. Journal of Soviet Mathematics, 20:2280\u20132289, 1982. Translation from Zap. Nauk. Sem. Lening. Otd. Mat. Inst., V. A. Steklova AN SSSR, Vol. 88, pp. 30\u201346, 1979.","journal-title":"Journal of Soviet Mathematics"},{"key":"6_CR9","unstructured":"J.H. Bennett. On Spectra. PhD thesis, Princeton University, 1962. Department of Mathematics."},{"issue":"2","key":"6_CR10","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01202288","volume":"4","author":"S. Bloch","year":"1994","unstructured":"S. Bloch. Function-algebraic characterizations of log and polylog parallel time. Computational Complexity, 4(2):175\u2013205, 1994.","journal-title":"Computational Complexity"},{"key":"6_CR11","unstructured":"S. Buss. Bounded Arithmetic, volume 3 of Studies in Proof Theory. Bibliopolis, 1986. 221 pages."},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"S. Buss. The polynomial hierarchy and intuitionistic bounded arithmetic. In A.L. Selman, editor, Structure in Complexity Theory, volume 223, pages 77\u2013103. 1986. Springer Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-16486-3_91"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"J.-Y. Cai and M.L. Furst. PSPACE survives three-bit bottlenecks. In Proceedings of 3th Annual IEEE Conference on Structure in Complexity Theory, pages 94\u2013102, 1988.","DOI":"10.1109\/PSCT.1987.10319258"},{"key":"6_CR14","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. J. Stockmeyer. Alternation. Journal of the Association of Computing Machinery, 28:114\u2013133, 1981.","journal-title":"Journal of the Association of Computing Machinery"},{"key":"6_CR15","doi-asserted-by":"crossref","first-page":"345","DOI":"10.2307\/2371045","volume":"58","author":"A. Church","year":"1936","unstructured":"A. Church. An unsolvable problem in elementary number theory. American Journal of Mathematics, 58:345\u2013363, 1936.","journal-title":"American Journal of Mathematics"},{"key":"6_CR16","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF02835830","volume":"25","author":"P. Clote","year":"1992","unstructured":"P. Clote. A time-space hierarchy between P and PSPACE. Mathematical Systems Theory, 25:77\u201392, 1992.","journal-title":"Mathematical Systems Theory"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"P. Clote. Polynomial size frege proofs of certain combinatorial principles. In P. Clote and J. Kraj\u00ed\u010dek, editors, Arithmetic, Proof Theory and Computational Complexity, pages 162\u2013184. Oxford University Press, 1993.","DOI":"10.1093\/oso\/9780198536901.003.0007"},{"key":"6_CR18","unstructured":"P. Clote. Nondeterministic stack register machines. Submitted."},{"key":"6_CR19","unstructured":"P. Clote, B. Kapron, and A. Ignjatovic. Parallel computable higher type functionals. Technical Report BCCS-94-04, Department of Computer Science, Boston College, June 1994."},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"P. Clote, B. Kapron, and A. Ignjatovic. Parallel computable higher type functionals. In Proceedings of IEEE 34th Annual Symposium on Foundations of Computer Science, Nov 3\u20135, 1993. Palo Alto CA. pp. 72\u201383.","DOI":"10.1109\/SFCS.1993.366880"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"P. Clote and G. Takeuti. Exponential time and bounded arithmetic. In A.L. Selman, editor, Structure in Complexity Theory, volume 223, pages 125\u2013143. Springer Lecture Notes in Computer Science, 1986.","DOI":"10.1007\/3-540-16486-3_94"},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0168-0072(92)90068-B","volume":"56","author":"P. Clote","year":"1992","unstructured":"P. Clote and G. Takeuti. Bounded arithmetics for NC, ALOGTIME, L and NL. Annals of Pure and Applied Logic, 56:73\u2013117, 1992.","journal-title":"Annals of Pure and Applied Logic"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"P. Clote and G. Takeuti. First order bounded arithmetic and small boolean circuit complexity classes. In P. Clote and J. Remmel, editors, Feasible Mathematics II, pages 154\u2013218. Birkh\u00e4user Boston Inc., 1995.","DOI":"10.1007\/978-1-4612-2566-9_6"},{"key":"6_CR24","unstructured":"P.G. Clote. A sequential characterization of the parallel complexity class NC Technical Report BCCS-88-07, Department of Computer Science, Boston College, 1988."},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"P.G. Clote. Sequential, machine-independent characterizations of the parallel complexity classes ALOGTIME, AC k, NCk and NC. In P.J. Scott S.R. Buss, editor, Feasible Mathematics, pages 49\u201370. Birkh\u00e4user, 1990.","DOI":"10.1007\/978-1-4612-3466-1_4"},{"key":"6_CR26","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":"6_CR27","doi-asserted-by":"crossref","unstructured":"R. Constable. Type 2 computational complexity. In 5th Annual ACM Symposium on Theory of Computing, 1973. pp. 108\u2013121.","DOI":"10.1145\/800125.804041"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"S. Cook. Computability and complexity of higher type functions. In Y.N. Moschovakis, editor, Logic from Computer Science, pages 51\u201372. Springer Verlag, 1992.","DOI":"10.1007\/978-1-4612-2822-6_3"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"S.A. Cook and B.M. Kapron. Characterizations of the feasible functional of finite type. In P.J. Scott S.R. Buss, editor, Feasible Mathematics, pages 71\u201398. Birkh\u00e4user, 1990.","DOI":"10.1007\/978-1-4612-3466-1_5"},{"issue":"2","key":"6_CR30","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0168-0072(93)90044-E","volume":"63","author":"S.A. Cook","year":"1993","unstructured":"S.A. Cook and A. Urquhart. Functional interpretations of feasibly constructive arithmetic. Annals of Pure and Applied Logic, 63(2):pp. 103\u2013200, 1993.","journal-title":"Annals of Pure and Applied Logic"},{"key":"6_CR31","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, pages 43\u201373, 1974."},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"R. Fagin. Finite-model theory\u2014a personal perspective. In S. Abiteboul and P. Kanellakis, editors, Proc. 1990 International Conference on Database Theory, pages 3\u201324. Springer-Verlag Lecture Notes in Computer Science 470, 1990. Journal version to appear in Theoretical Computer Science.","DOI":"10.1007\/3-540-53507-1_67"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie. Parallelism in random access machines. In 10th Annual ACM Symposium on Theory of Computing, 1978. pp. 114\u2013118.","DOI":"10.1145\/800133.804339"},{"key":"6_CR34","doi-asserted-by":"crossref","unstructured":"J.-Y. Girard, A. Scedrov, and P. Scott. Bounded linear logic. In P.J. Scott S.R. Buss, editor, Feasible Mathematics, pages 195\u2013210. Birkh\u00e4user, 1990.","DOI":"10.1007\/978-1-4612-3466-1_11"},{"key":"6_CR35","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01700692","volume":"38","author":"K. G\u00f6del","year":"1931","unstructured":"K. G\u00f6del. \u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme. J. Monat. Math. Phys., 38:173\u2013198, 1931.","journal-title":"J. Monat. Math. Phys."},{"key":"6_CR36","unstructured":"K. G\u00f6del. Conversation with G.E. Sacks. Institute for Advanced Study, 1975."},{"key":"6_CR37","unstructured":"L. Goldschlager. Synchronous parallel computation. Technical Report 114, University of Toronto, December 1977. 131 pages."},{"issue":"4","key":"6_CR38","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"L. Goldschlager","year":"1982","unstructured":"L. Goldschlager. A unified approach to models of synchronous parallel machines. Journal of the Association of Computing Machinery, 29(4):pp. 1073\u20131086, October 1982.","journal-title":"Journal of the Association of Computing Machinery"},{"key":"6_CR39","unstructured":"A. Grzegorczyk. Some clases of recursive functions. Rozprawy Matematyczne, 4, 1953."},{"key":"6_CR40","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Algebras of feasible functions. In Proceedings of 24th IEEE Symposium on Foundations of Computer Science, 1983. pp. 210\u2013214.","DOI":"10.1109\/SFCS.1983.5"},{"key":"6_CR41","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/3-540-51237-3_10","volume":"363","author":"Y. Gurevich","year":"1989","unstructured":"Y. Gurevich and S. Shelah. Nearly linear time. Symposium on Logical Foundations of Computer Science, Springer Lecture Notes in Computer Science(363):108\u2013118, 1989. Pereslavl-Zalessky, USSR.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"6_CR42","series-title":"Colloquia Societatis Janos Bolyai","first-page":"353","volume-title":"Theory of Algorithms","author":"W. Handley","year":"1984","unstructured":"W. Handley, J. B. Paris, and A. J. Wilkie. Characterizing some low arithmetic classes. In Theory of Algorithms, pages 353\u2013364. Akademie Kyado, Budapest, 1984. Colloquia Societatis Janos Bolyai."},{"key":"6_CR43","unstructured":"W.G. Handley. LTH plus nondeterministic summation mod M 3 yields ALIN-TIME. Submitted, 22 December 1994."},{"key":"6_CR44","unstructured":"W.G. Handley. Deterministic summation modulo \u03b2 n, the semi-group of binary relations on 1, {O, ..., n\u22121}. Submitted, May 1994."},{"issue":"2","key":"6_CR45","doi-asserted-by":"crossref","first-page":"466","DOI":"10.2307\/2275282","volume":"57","author":"V. Harnik","year":"1992","unstructured":"V. Harnik. Provably total functions of intuitionistic bounded arithmetic. Journal of Symbolic Logic, 57(2):466\u2013477, 1992.","journal-title":"Journal of Symbolic Logic"},{"key":"6_CR46","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1002\/malq.19750210157","volume":"21","author":"K. Harrow","year":"1975","unstructured":"K. Harrow. Small Grzegorczyk classes and limited minimum. Zeit. Math. Logik, 21:417\u2013426, 1975.","journal-title":"Zeit. Math. Logik"},{"key":"6_CR47","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/malq.19790252506","volume":"25","author":"K. Harrow","year":"1979","unstructured":"K. Harrow. Equivalence of some hierarchies of primitive recursive functions. Zeit. Math. Logik, 25:411\u2013418, 1979.","journal-title":"Zeit. Math. Logik"},{"key":"6_CR48","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01206605","volume":"95","author":"D. Hilbert","year":"1925","unstructured":"D. Hilbert. \u00dcber das Unendliche. Mathematische Annalen, 95:161\u2013190, 1925.","journal-title":"Mathematische Annalen"},{"key":"6_CR49","unstructured":"H. James Hoover. Feasibly constructive analysis. Technical Report 206\/87, University of Toronto, November 1987. 114 pages."},{"key":"6_CR50","doi-asserted-by":"crossref","unstructured":"H.J. Hoover. Computational models for feasible real analysis. In S.R. Buss and P.J. Scott, editors, Feasible Mathematics, pages 221\u2013238. Birkh\u00e4user, 1990.","DOI":"10.1007\/978-1-4612-3466-1_13"},{"key":"6_CR51","unstructured":"A. Ignjatovic. Some applications of logic to feasibility in higher types. Typescript and invited talk at meeting LCC, Indianapolis, organizer D. Leivant, October 13\u201316 1994."},{"key":"6_CR52","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal of Computing, 16:760\u2013778, 1987.","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"6_CR53","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"N. Immerman. Expressibility and parallel complexity. SIAM J. Comput., 18(3):625\u2013638, 1989.","journal-title":"SIAM J. Comput."},{"key":"6_CR54","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N.D. Jones","year":"1974","unstructured":"N.D. Jones and A.L. Selman. Turing machines and the spectra of first-order formulas. Journal of Symbolic Logic, 39:139\u2013150, 1974.","journal-title":"Journal of Symbolic Logic"},{"key":"6_CR55","first-page":"1","volume":"50","author":"L. Kalmar","year":"1943","unstructured":"L. Kalmar. Egyszer\u00fc p\u00e9lda eld\u00f6nthetetlen aritmetikai probl\u00e9m\u00e1ra. Mate \u00e9s Fizikai Lapok, 50:1\u201323, 1943. [In Hungarian with German abstract].","journal-title":"Mate \u00e9s Fizikai Lapok"},{"key":"6_CR56","doi-asserted-by":"crossref","unstructured":"B. Kapron and S. Cook. A new characterization of Mehlhorn's poly time functionals. In Proceedings of IEEE 32th Annual Symposium on Foundations of Computer Science, pages pp. 342\u2013347, 1991. to appear in SIAM J. on Comput.","DOI":"10.1109\/SFCS.1991.185389"},{"key":"6_CR57","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1007\/BF01565439","volume":"112","author":"S.C. Kleene","year":"1936","unstructured":"S.C. Kleene. General recursive functions of natural numbers. Math. Ann., 112:727\u2013742, 1936.","journal-title":"Math. Ann."},{"key":"6_CR58","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1215\/S0012-7094-36-00227-2","volume":"2","author":"S.C. Kleene","year":"1936","unstructured":"S.C. Kleene. Lambda-definability and recursiveness. Duke Mathematical Journal, 2:340\u2013353, 1936.","journal-title":"Duke Mathematical Journal"},{"key":"6_CR59","unstructured":"Ker-I Ko. Applying techniques of discrete complexity theory to numerical computation. In R.V. Book, editor, Studies in Complexity Theory, pages 1\u201362. John Wiley and Sons, Inc, 1986."},{"key":"6_CR60","unstructured":"G. Kreisel, D. Lacombe, and J.R. Shoenfield. Partial recursive functionals and effective operations. In A. Heyting, editor, Constructivity in Mathematics: Proceedings of a colloquium held in Amsterdam, pages 195\u2013207. North Holland, 1957."},{"issue":"1","key":"6_CR61","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1017\/S0022481200029078","volume":"53","author":"M. Kuty\u0142owski","year":"1988","unstructured":"M. Kuty\u0142owski. Finite automata, real time processes and counting problems in bounded arithmetics. Journal of Symbolic Logic, 53(1):243\u2013258, 1988.","journal-title":"Journal of Symbolic Logic"},{"key":"6_CR62","doi-asserted-by":"crossref","unstructured":"D. Leivant. Ramified recurrence and computational complexity I: word recurrence and poly-time. In P. Clote and J. Remmel, editors, Feasible Mathematics II, pages 320\u2013343. Birkh\u00e4user, 1994.","DOI":"10.1007\/978-1-4612-2566-9_11"},{"key":"6_CR63","doi-asserted-by":"crossref","first-page":"167","DOI":"10.3233\/FI-1993-191-207","volume":"19","author":"D. Leivant","year":"1993","unstructured":"D. Leivant and J.-Y. Marion. Lambda-calculus characterizations of poly-time. Fundamenta Informaticae, 19:167\u2013184, 1993.","journal-title":"Fundamenta Informaticae"},{"key":"6_CR64","unstructured":"J.C. Lind. Computing in logarithmic space. Technical Report Project MAC Technical Memorandum 52, Massachusetts Institute of Technology, September 1974."},{"key":"6_CR65","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(76)80035-9","volume":"12","author":"K. Mehlhorn","year":"1976","unstructured":"K. Mehlhorn. Polynomial and abstract subrecursive classes. Journal of Computer and System Science, 12:147\u2013178, 1976.","journal-title":"Journal of Computer and System Science"},{"key":"6_CR66","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0304-3975(76)90065-7","volume":"3","author":"B. Monien","year":"1977","unstructured":"B. Monien. A recursive and grammatical characterization of exponential time languages. Theoretical Computer Science, 3:61\u201374, 1977.","journal-title":"Theoretical Computer Science"},{"key":"6_CR67","unstructured":"A. Nerode, J. Remmel, and A. Scedrov. Polynomially graded logic I \u2014 a graded version of system T. In Proceedings of IEEE 4th Annual Symposium on Logic in Computer Science, 1989."},{"key":"6_CR68","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01387405","volume":"32","author":"K.-H. Niggl","year":"1993","unstructured":"K.-H. Niggl. Subrecursive hierarchies on Scott domains. Archive for Mathematical Logic, 32:239\u2013257, 1993.","journal-title":"Archive for Mathematical Logic"},{"key":"6_CR69","unstructured":"J. Otto. Tiers, tensors, and \u0394 0 0 . Talk at meeting LCC, Indianapolis, organizer D. Leivant, October 13\u201316 1994."},{"key":"6_CR70","first-page":"176","volume":"VIII","author":"S.V. Pakhomov","year":"1979","unstructured":"S.V. Pakhomov. Machine independent description of some machine complexity classes (in Russian). Issledovanija po konstrukt. matermat, i mat. logike, VIII:176\u2013185, LOMI 1979.","journal-title":"Issledovanija po konstrukt. matermat, i mat. logike"},{"key":"6_CR71","doi-asserted-by":"crossref","unstructured":"J. B. Paris and A. J. Wilkie. Counting problems in bounded arithmetic. In C. A. di Prisco, editor, Methods in Mathematical Logic, pages 317\u2013340. Springer Verlag Lecture Notes in Mathematics, 1983. Proceedings of Logic Conference held in Caracas, 1983.","DOI":"10.1007\/BFb0075316"},{"key":"6_CR72","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/BF01571648","volume":"113","author":"R. P\u00e9ter","year":"1936","unstructured":"R. P\u00e9ter. \u00dcber die mehrfache Rekursion. Mathematische Annalen, 113:489\u2013526, 1936.","journal-title":"Mathematische Annalen"},{"key":"6_CR73","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/S0002-9947-1963-0158822-2","volume":"106","author":"R.W. Ritchie","year":"1963","unstructured":"R.W. Ritchie. Classes of predictably computable functions. Trans. Am. Math. Soc., 106:139\u2013173, 1963.","journal-title":"Trans. Am. Math. Soc."},{"key":"6_CR74","doi-asserted-by":"crossref","first-page":"98","DOI":"10.2307\/2266510","volume":"14","author":"J. Robinson","year":"1949","unstructured":"J. Robinson. Definability and decision problems in arithmetic. Journal of Symbolic Logic, 14:98\u2013114, 1949.","journal-title":"Journal of Symbolic Logic"},{"key":"6_CR75","first-page":"191","volume-title":"volume 9 of Oxford Logic Guides","author":"H. E. Rose","year":"1984","unstructured":"H. E. Rose. Subrecursion: Function and Hierarchies, volume 9 of Oxford Logic Guides. Clarendon Press, Oxford, 1984. 191 pages."},{"key":"6_CR76","unstructured":"J.S. Royer. Semantics vs. syntax vs. computation. Typescript, November 29, 1994."},{"key":"6_CR77","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W.L. Ruzzo","year":"1981","unstructured":"W.L. Ruzzo. On uniform circuit complexity. J. Comput. System Sci., 22:pp. 365\u2013383, 1981.","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"6_CR78","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 Association of Computing Machinery, 25(1):136\u2013145, 1978.","journal-title":"Journal of the Association of Computing Machinery"},{"key":"6_CR79","doi-asserted-by":"crossref","first-page":"160","DOI":"10.2307\/2266243","volume":"17","author":"H. Scholz","year":"1952","unstructured":"H. Scholz. Ein ungel\u00f6stes Problem in der symbolischen Logik. Journal of Symbolic Logic, 17:160, 1952.","journal-title":"Journal of Symbolic Logic"},{"key":"6_CR80","doi-asserted-by":"crossref","unstructured":"H. Schwichtenberg. Primitive recursion on the partial continuous functionals. In M. Broy, editor, Informatik und Mathematik, pages 251\u2013259. Springer-Verlag, 1991.","DOI":"10.1007\/978-3-642-76677-0_18"},{"key":"6_CR81","doi-asserted-by":"crossref","unstructured":"A. Seth. There is no recursive axiomatization for feasible functionals of type 2. In Proceedings of IEEE 7th Annual Symposium on Logic in Computer Science, 1992. pp. 286\u2013295.","DOI":"10.1109\/LICS.1992.185541"},{"key":"6_CR82","unstructured":"A. Seth. Some desirable conditions for feasible functionals of type 2. In Proceedings of IEEE 8th Annual Symposium on Logic in Computer Science, 1993."},{"key":"6_CR83","doi-asserted-by":"crossref","unstructured":"A. Seth. Turing machine characterizations of feasible functionals of all finite types. In P. Clote and J. Remmel, editors, Feasible Mathematics II, pages 407\u2013428. Birkh\u00e4user, 1994.","DOI":"10.1007\/978-1-4612-2566-9_14"},{"key":"6_CR84","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin. Finding the maximum, merging and sorting in a parallel computation model. Journal of Algorithms, 3:57\u201367, 1982.","journal-title":"Journal of Algorithms"},{"key":"6_CR85","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"L. Stockmeyer and U. Vishkin. Simulation of parallel random access machines by circuits. SIAM Journal on Computing, 13:409\u2013422, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"6_CR86","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01706069","volume":"6","author":"D.B. Thompson","year":"1972","unstructured":"D.B. Thompson. Subrecursiveness: machine independent notions of computability in restricted time and storage. Math. Systems Theory, 6:3\u201315, 1972.","journal-title":"Math. Systems Theory"},{"key":"6_CR87","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1305\/ndjfl\/1093635419","volume":"31","author":"M. Townsend","year":"1990","unstructured":"M. Townsend. Complexity for type-2 relations. Notre Dame Journal of Formal Logic, 31:241\u2013262, 1990.","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"6_CR88","first-page":"230","volume":"42","author":"A.M. Turing","year":"1936\u201337","unstructured":"A.M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc., Series 2, 42:230\u2013265, 1936\u201337.","journal-title":"Proc. Lond. Math. Soc., Series 2"},{"key":"6_CR89","doi-asserted-by":"crossref","unstructured":"K. Wagner. Bounded recursion and complexity classes. In Lecture Notes in Computer Science, volume 74, pages 492\u2013498. Springer-Verlag, 1979.","DOI":"10.1007\/3-540-09526-8_49"},{"key":"6_CR90","unstructured":"K. Wagner and G. Wechsung. Computational Complexity. Reidel Publishing Co., 1986."},{"key":"6_CR91","doi-asserted-by":"crossref","unstructured":"A. Woods. Bounded arithmetic formulas and Turing machines of constant alternation. In J.B. Paris, A.J. Wilkie, and G.M. Wilmers, editors, Logic Coloquium 1984. North Holland, 1986.","DOI":"10.1016\/S0049-237X(08)70471-3"},{"key":"6_CR92","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"C. Wrathall. Complete sets and the polynomial time hierarchy. Theoretical Computer Science, 3:23\u201333, 1976.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_81","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:55:01Z","timestamp":1742597701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_81"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":92,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_81","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}