Publication:4934292
From MaRDI portal
zbMath0942.68049MaRDI QIDQ4934292
Publication date: 13 July 2000
survey; function algebra; complexity classes; computation model; primitive recursive functions; recursion scheme; computable function; quantifier hierarchies; type 2 functional
03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D20: Recursive functions and relations, subrecursive hierarchies
03D10: Turing machines and related notions
Related Items
A proof-theoretic characterization of the basic feasible functionals, Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\), A foundation for real recursive function theory, Implicit characterizations of FPTIME and NC revisited, Theories with self-application and computational complexity., Continuous-time computation with restricted integration capabilities, Safe recursion with higher types and BCK-algebra, A survey of recursive analysis and Moore's notion of real computation, Separating NC along the \(\delta\) axis, On the computational complexity of imperative programming languages, An analog characterization of the Grzegorczyk hierarchy, A characterization of alternating log time by ramified recurrence, A Characterisation of the Relations Definable in Presburger Arithmetic, Pure Iteration and Periodicity
