New Computational Paradigms

DOI10.1007/B136981MaRDI QIDQ5717048zbMATH OpenOpenAlexFDO

Authors Lars Kristiansen, Mathias Barra

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b136981

zbMATH Keywords

complexity classesfragments of typed \(\lambda\)-calculusimplicit characterisationsrudimentary relationssmall relational Grzegorczyk classes

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Small Grzegorczyk Classes
• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
• Logical Approaches to Computational Barriers
• Characterization of the Relations in Grzegorczyk's Hierarchy Revisited

Cited in

(7)

• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• A Characterisation of the Relations Definable in Presburger Arithmetic
• Pure Iteration and Periodicity
• Recursion in Higher Types and Resource Bounded Turing Machines
• Logical Approaches to Computational Barriers
• Non-determinism in Gödel's system \(T\)

This page was built for publication: New Computational Paradigms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5717048)