Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)

DOI10.1007/s00224-007-9021-xzbMath1166.03018OpenAlexW2084909062MaRDI QIDQ1015376

Lars Kristiansen

Publication date: 8 May 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9021-x

zbMATH Keywords

typescomplexity theory\(\lambda\)-calculiGödel's \(T\)subrecursive classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (4)

Computational Complexity Via Finite Types ⋮ Practical synchronization of second-order nonautonomous systems with parameter mismatch and its applications ⋮ A Characterisation of the Relations Definable in Presburger Arithmetic ⋮ Non-determinism in Gödel's system \(T\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity classes and fragments of C
• Rudimentary relations and primitive recursion: A toolbox
• Characterizing complexity classes by higher type primitive recursive definitions
• Polynomial functions with exponentiation are well ordered
• An ordinal bound for the set of polynomial functions with exponentiation
• Classical recursion theory. Vol. II
• Neat function algebraic characterizations of LOGSPACE and LINSPACE
• The expressive power of higher-order types or, life without CONS
• Classes of Predictably Computable Functions
• Some Relations between Classes of Low Computational Complexity
• Small Grzegorczyk Classes
• Computer Science Logic
• New Computational Paradigms
• Logical Approaches to Computational Barriers
• Theory and Applications of Models of Computation

This page was built for publication: Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)