Higher type recursion, ramification and polynomial time

DOI10.1016/S0168-0072(00)00006-3zbMATH Open0959.03027OpenAlexW1970954854MaRDI QIDQ1577477FDOQ1577477

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

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

Recommendations

• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• scientific article; zbMATH DE number 2006627
• Recursion in Higher Types and Resource Bounded Turing Machines
• Characterizing complexity classes by general recursive definitions in higher types
• scientific article; zbMATH DE number 4170889
• Higher recursion theory
• scientific article; zbMATH DE number 194101
• Higher type recursion for transfinite machine theory
• scientific article; zbMATH DE number 65741
• Characterizing complexity classes by higher type primitive recursive definitions

zbMATH Keywords

lambda calculusnormalisationhigher type recursionpolynomial-time computable functionsramified recursion

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (39)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Higher-order interpretations and program complexity
• A semantic proof of polytime soundness of light affine logic
• Automated higher-order complexity analysis
• Title not available (Why is that?)
• An arithmetic for polynomial-time computation
• Type inference for light affine logic via constraints on words
• Adventures in time and space
• Realizability models and implicit complexity
• The geometry of linear higher-order recursion
• Light affine lambda calculus and polynomial time strong normalization
• Adventures in time and space
• Computer Science Logic
• Implicit computation complexity in higher-order programming languages
• Linear types and non-size-increasing polynomial time computation.
• Build your own clarithmetic. I: Setup and completeness
• Objects in polynomial time
• Characterizing parallel time by type 2 recursions with polynomial output length
• The Garland measure and computational complexity of stack programs
• A higher-order characterization of probabilistic polynomial time
• Title not available (Why is that?)
• Types for Proofs and Programs
• Title not available (Why is that?)
• A proof-theoretic characterization of the basic feasible functionals
• Cyclic implicit complexity
• Implicit characterizations of FPTIME and NC revisited
• Theories with self-application and computational complexity.
• Title not available (Why is that?)
• Polytime, combinatory logic and positive safe induction
• Title not available (Why is that?)
• On sharing, memoization, and polynomial time
• On sharing, memoization, and polynomial time
• Control structures in programs and computational complexity
• On the computational complexity of imperative programming languages
• Title not available (Why is that?)
• Separating NC along the \(\delta\) axis
• Title not available (Why is that?)
• An arithmetic for non-size-increasing polynomial-time computation

This page was built for publication: Higher type recursion, ramification and polynomial time

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