scientific article; zbMATH DE number 806752

Publication date: 27 August 1996

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

bounded arithmetic Turing machine register machine word functions primitive recursive functions subrecursive hierarchies complexity classes of number-theoretical functions Ramified Recurrence recurrence nesting degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items (46)

Higher-order interpretations and program complexity ⋮ Algebraic and logical characterizations of deterministic linear time classes ⋮ V-comprehensions and P space ⋮ On sharing, memoization, and polynomial time ⋮ Characterizing polynomial and exponential complexity classes in elementary lambda-calculus ⋮ Algorithmically broad languages for polynomial time and space ⋮ Light affine lambda calculus and polynomial time strong normalization ⋮ Computational Complexity Via Finite Types ⋮ Computation models and function algebras ⋮ Intrinsic theories and computational complexity ⋮ Characterizing parallel time by type 2 recursions with polynomial output length ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Read/write factorizable programs ⋮ A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations ⋮ Analysing the implicit complexity of programs. ⋮ Unnamed Item ⋮ Build your own clarithmetic I: Setup and completeness ⋮ Theories with self-application and computational complexity. ⋮ A characterization of alternating log time by ramified recurrence ⋮ Quasi-interpretations. A way to control resources ⋮ Ramified Corecurrence and Logspace ⋮ Implicit complexity over an arbitrary structure: Quantifier alternations ⋮ A proof-theoretic characterization of the basic feasible functionals ⋮ Resource control for synchronous cooperative threads ⋮ Unnamed Item ⋮ Intrinsic reasoning about functional programs. I: First order theories ⋮ Two algorithms in search of a type-system ⋮ Light types for polynomial time computation in lambda calculus ⋮ Tiered Arithmetics ⋮ Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets ⋮ A note on complexity measures for inductive classes in constructive type theory ⋮ Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations ⋮ Separating NC along the \(\delta\) axis ⋮ Automated higher-order complexity analysis ⋮ Minimization and \(\mathbf{NP}\) multifunctions ⋮ On the computational complexity of imperative programming languages ⋮ Feasible functionals and intersection of ramified types ⋮ Higher type recursion, ramification and polynomial time ⋮ Implicit characterizations of FPTIME and NC revisited ⋮ Linear logic by levels and bounded time complexity ⋮ A decidable characterization of the classes between lintime and exptime ⋮ Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity ⋮ Implicit recursion-theoretic characterizations of counting classes ⋮ On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy ⋮ A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations ⋮ A new order-theoretic characterisation of the polytime computable functions

This page was built for publication: