Higher type recursion, ramification and polynomial time

DOI10.1016/S0168-0072(00)00006-3MaRDI QIDQ1577477zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3909745 (Why is no real title available?)
• scientific article; zbMATH DE number 176200 (Why is no real title available?)
• scientific article; zbMATH DE number 176211 (Why is no real title available?)
• scientific article; zbMATH DE number 1223626 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• scientific article; zbMATH DE number 1499100 (Why is no real title available?)
• scientific article; zbMATH DE number 949290 (Why is no real title available?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited
• Short proofs of normalization for the simply-typed \(\lambda\)-calculus, permutative conversions and Gödel's \(\mathbf T\)
• The realm of primitive recursion
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES

Cited in

(39)

• An arithmetic for non-size-increasing polynomial-time computation
• Higher-order interpretations and program complexity
• scientific article; zbMATH DE number 4170889 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• A semantic proof of polytime soundness of light affine logic
• Automated higher-order complexity analysis
• Type inference for light affine logic via constraints on words
• An arithmetic for polynomial-time computation
• scientific article; zbMATH DE number 2110623 (Why is no real title available?)
• Realizability models and implicit complexity
• Adventures in time and space
• 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
• The Garland measure and computational complexity of stack programs
• Characterizing parallel time by type 2 recursions with polynomial output length
• A higher-order characterization of probabilistic polynomial time
• scientific article; zbMATH DE number 2006627 (Why is no real title available?)
• Types for Proofs and Programs
• scientific article; zbMATH DE number 4179364 (Why is no real title available?)
• A proof-theoretic characterization of the basic feasible functionals
• Implicit characterizations of FPTIME and NC revisited
• Cyclic implicit complexity
• Theories with self-application and computational complexity.
• Polytime, combinatory logic and positive safe induction
• scientific article; zbMATH DE number 1424029 (Why is no real title available?)
• On sharing, memoization, and polynomial time
• Control structures in programs and computational complexity
• On sharing, memoization, and polynomial time
• scientific article; zbMATH DE number 1531370 (Why is no real title available?)
• On the computational complexity of imperative programming languages
• scientific article; zbMATH DE number 1808199 (Why is no real title available?)
• Separating NC along the \(\delta\) axis
• scientific article; zbMATH DE number 176200 (Why is no real title available?)

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)