Higher type recursion, ramification and polynomial time

DOI10.1016/S0168-0072(00)00006-3zbMath0959.03027OpenAlexW1970954854MaRDI QIDQ1577477

Helmut Schwichtenberg, Stephen J. Bellantoni, Karl-Heinz Niggl

Publication date: 4 September 2000

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(00)00006-3

zbMATH Keywords

lambda calculusnormalisationhigher type recursionpolynomial-time computable functionsramified recursion

Mathematics Subject Classification ID

Theory of programming languages (68N15) Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Functionals in proof theory (03F10) Second- and higher-order arithmetic and fragments (03F35) Proof theory in general (including proof-theoretic semantics) (03F03) Combinatory logic and lambda calculus (03B40) Higher-type and set recursion theory (03D65)

Related Items

Higher-order interpretations and program complexity, Light affine lambda calculus and polynomial time strong normalization, Build your own clarithmetic I: Setup and completeness, Theories with self-application and computational complexity., The Garland Measure and Computational Complexity of Stack Programs, Realizability models and implicit complexity, Type inference for light affine logic via constraints on words, A proof-theoretic characterization of the basic feasible functionals, Control structures in programs and computational complexity, An arithmetic for polynomial-time computation, A semantic proof of polytime soundness of light affine logic, An arithmetic for non-size-increasing polynomial-time computation, Separating NC along the \(\delta\) axis, Automated higher-order complexity analysis, On the computational complexity of imperative programming languages, Implicit characterizations of FPTIME and NC revisited, A higher-order characterization of probabilistic polynomial time, Implicit computation complexity in higher-order programming languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The realm of primitive recursion
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Short proofs of normalization for the simply-typed \(\lambda\)-calculus, permutative conversions and Gödel's \(\mathbf T\)
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited