Abstract
The class \(\Delta^\mathbb{N}_{0}\) of rudimentary relations and the small relational Grzegorczyk classes \(\varepsilon^{0}_{*}, \varepsilon^{1}_{*}, \varepsilon^{2}_{*}\) attracted fairly much attention during the latter half of the previous century, e.g. Gandy [6], Paris-Wilkie [20], and numerous others.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beckmann, A., Weiermann, A.: Characterizing the elementary recursive functions by a fragment of Gödel’s T. Arch. Math. Logic 39(7), 475–491 (2000)
Bellantoni, S.J., Cook, S.: A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity 2, 7–110 (1992)
Bel’tyukov, A.P.: A machine description and the hierarchy of initial Grzegorczyk classes. Zap. Naucn. Sem. Leninigrad. Otdel. May. Inst. Steklov. (LOMI) 88, 30–46 (1979); J. Soviet Math. 20 (1982)
Clote, P.: Computation Models and Function Algebra. In: Griffor, E. (ed.) Handbook of Computability Theory. Elsevier, Amsterdam (1996)
Esbelin, M.-A., More, M.: Rudimentary relations and primitive recursion: A toolbox. Theoretical Computer Science 193, 129–148 (1998)
Gandy, R.: Some relations between classes of low computational complexity. Bulletin of London Mathematical Society, 127–134 (1984)
Grzegorczyk, A.: Some classes of recursive functions. Rozprawy Matematyczne, No. IV, Warszawa (1953)
Harrow, K.: Sub-elementary classes of functions and relations. Doctoral Dissertation, New York University, Department of Mathematics (1973)
Hindley, J.R., Seldin, J.P.: Introduction to Combinators and λ-caclulus. London Mathematical Society, Student Texts, vol. 1. Cambridge University Press, Cambridge (1984)
Jones, N.D.: The expressive power of higher-order types or, life without CONS. J. Functional Programming 11, 55–94 (2001)
Jones, N.D.: LOGSPACE and PTIME characterized by programming languages. Theoretical Computer Science 228, 151–174 (1999)
Kristiansen, L.: Neat function algebraic characterizations of LOGSPACE and LINSPACE. Computational Complexity (accepted)
Kristiansen, L., Niggl, K.-H.: On the computational complexity of imperative programming languages. Theoretical Computer Science 318, 139–161 (2004)
Kristiansen, L., Voda, P.J.: Complexity classes and fragments of C. Information Processing Letters 88, 213–218 (2003)
Kristiansen, L., Voda, P.J.: The surprising power of restricted programs and Gödel’s functionals. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol. 2803, pp. 345–358. Springer, Heidelberg (2003)
Kristiansen, L., Voda, P.J.: Programming languages capturing complexity classes (Submitted)
Kutylowski, M.: Small Grzegorczyk classes. J. London Math. Soc. 36(2), 193–210 (1987)
Leivant, D.: Intrinsic theories and computational complexity. In: Leivant, D. (ed.) LCC 1994. LNCS, vol. 960, pp. 177–194. Springer, Heidelberg (1995)
Odifreddi, P.: Classical Recursion Theory, vol. II. North-Holland, Amsterdam (1999)
Paris, J.B., Wilkie, A.: Counting problems in bounded arithmetic. In: Methods in mathematical logic. Proceedings, Caracas 1983. Lecture Notes in Mathematics, vol. 1130, pp. 317–340. Springer, Heidelberg (1985)
Ritchie, R.W.: Classes of predictably computable functions. Trans. Am. Math. Soc. 106, 139–173 (1963)
Rose, H.E.: Subrecursion. Functions and hierarchies. Clarendon Press, Oxford (1984)
Simmons, H.: The realm of primitive recursion. Arch. Math. Logic 27, 177–188 (1988)
Simmons, H.: Derivation and computation. Taking the Curry-Howard correspondence seriously. Cambridge Tracts in Theoretical Computer Science, vol. 51. Cambridge University, Cambridge (2000)
Terese: Term Rewriting Systems. Cambridge University Press, Cambridge (2003); Bezem, M., Klop, J.W., de Vrijer, R. (eds.)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kristiansen, L., Barra, M. (2005). The Small Grzegorczyk Classes and the Typed λ-Calculus. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds) New Computational Paradigms. CiE 2005. Lecture Notes in Computer Science, vol 3526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494645_32
Download citation
DOI: https://doi.org/10.1007/11494645_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26179-7
Online ISBN: 978-3-540-32266-5
eBook Packages: Computer ScienceComputer Science (R0)