Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-08T16:41:14.524Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounded minimalisation and bounded counting in argument-bounded idc's

Published online by Cambridge University Press:  27 October 2010

MATHIAS BARRA
MATHIAS BARRA*
Affiliation:
Department of Mathematics, University of Oslo, P.B. 1053, Blindern, 0316 Oslo, Norway Email: georgba@math.uio.no
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We define and investigate a number of small inductively defined classes (idc's), à la Gregorczyk, that are based on argument-bounded initial functions and the bounded minimalisation and bounded counting schemata. We establish equivalences between these and other classes in the literature, with an emphasis on minimalism. We also obtain characterisations of the classes in terms of well-known fragments of first-order predicate logic.

References

Barra, M. (2008) A characterisation of the relations definable in Presburger Arithmetic. In: Theory and Applications of Models of Computation (Proceedings of the 5th Int. Conf. TAMC 2008, Xi'an, China, 25–29 April). Springer-Verlag Lecture Notes in Computer Science 4978 258–269.CrossRefGoogle Scholar
Bennett, J. H. (1962) On Spectra, Ph.D. thesis, Princeton University.Google Scholar
Clote, P. (1996) Computation Models and Function Algebra. In: Handbook of Computability Theory, Elsevier.Google Scholar
Enderton, H. B. (1972) A mathematical introduction to logic, Academic Press.Google Scholar
Esbelin, H.-A. (1994) Une classe minimale de fonctions recursives contenant les relations rudimentaires (in French). C. R. Acad. Sci. Paris Série I 319 (5)505–508.Google Scholar
Esbelin, H.-A. and More, M. (1998) Rudimentary relations and primitive recursion: a toolbox. Theoretical Computer Science 193 (1-2)129–148.Google Scholar
Grzegorczyk, A. (1953) Some classes of recursive functions. Rozprawy Matematyczne No. IV.Google Scholar
Harrow, K. (1973) Sub-elementary classes of functions and relations, Ph.D. Thesis, New York University.Google Scholar
Harrow, K. (1975) Small Grzegorczyk classes and limited minimum. Zeitscr. f. math. Logik und Grundlagen d. Math. 21 417–426.Google Scholar
Jones, N. D. (1999) logspace and ptime characterized by programming languages. Theoretical Computer Science 228 151–174.CrossRefGoogle Scholar
Jones, N. D. (2001) The expressive power of higher-order types, or life without CONS. J. Functional Programming 11 55–94.CrossRefGoogle Scholar
Kristiansen, L. (2005) Neat function algebraic characterizations of logspace and linspace. Computational Complexity 14 (1)72–88.Google Scholar
Kristiansen, L. (2006) Complexity-Theoretic Hierarchies Induced by Fragments of Gödel's T. Theory of Computing Systems (Available at http://www.springerlink.com/content/e53l54627x063685/).Google Scholar
Kristiansen, L. and Barra, M. (2005) The small Grzegorczyk classes and the typed λ-calculus, In: New Computational Paradigms. Springer-Verlag Lecture Notes in Computer Science 3526 252–262.Google Scholar
Kristiansen, L. and Voda, P. J. (2003a) The surprising power of restricted programs and Gödel's functionals. In: Computer Science Logic. Springer-Verlag Lecture Notes in Computer Science 2803 345–358.CrossRefGoogle Scholar
Kristiansen, L. and Voda, P. J. (2003b) Complexity classes and fragments of C. Information Processing Letters 88 213–218.Google Scholar
Kristiansen, L. and Voda, P. J. (2008) The structure of Detour Degrees. In: Theory and Applications of Models of Computation (Proceedings of the 5th Int. Conf. TAMC 2008, Xi'an, China, 25–29 April). Springer-Verlag Lecture Notes in Computer Science 4978 148–159.CrossRefGoogle Scholar
Lipton, R. J. (1979) Model theoretic aspects of computational complexity. In: Proc. 19th Annual Symp. on Foundations of Computer Science, IEEE Computer Society 193–200.Google Scholar
Paris, J. and Wilkie, A. (1985) Counting problems in bounded arithmetic In: Proceedings, Methods in mathematical logic, Caracas 1983. Springer-Verlag Lecture Notes in Mathematics 1130 317–340.Google Scholar
Presburger, M. (1930) Über die Vollständigket eines gewissen Systems der Arithmetik ganzer Zahlen in welchem die Addition als einzige Operation hervortritt. In: Sprawozdanie z I Kongresu Matematyków Słowańskich 92–101.Google Scholar
Presburger, M. and Jaquette, D. (1991) On the Completeness of a Certain System of Arithmetic of Whole Numbers in Which Addition Occurs as the Only Operation. History and Philosophy of Logic 12 225–233.CrossRefGoogle Scholar
Smullyan, R. M. (1961) Theory of formal systems (revised edition), Princeton University Press.CrossRefGoogle Scholar
Schweikardt, N. (2005) Arithmetic, First-Order Logic, and Counting Quantifiers. ACM Trans. Comp. Log. 6 (3)634–671.CrossRefGoogle Scholar
Wrathall, C. (1978) Rudimentary predicates and relative computation. SIAM J. Comput. 7 (2)194–209.CrossRefGoogle Scholar