Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity

DOI10.1016/S0168-0072(98)00040-2zbMath0924.03071OpenAlexW2013519208MaRDI QIDQ1295429

Daniel Leivant

Publication date: 20 July 1999

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(98)00040-2

zbMATH Keywords

computational complexityfunctionalsfeasibilityprimitive recursionapplicative programs with recurrence operatorsequational recurrencefunctional programs over free algebrashigher type functionshigher type recurrenceKalmar-elementary functionspurely applicative higher-type programsramified recurrence

Mathematics Subject Classification ID

Related Items (5)

Bounded combinatory logic and lower complexity ⋮ Computational Complexity Via Finite Types ⋮ Taming Modal Impredicativity: Superlazy Reduction ⋮ Tiering as a Recursion Technique ⋮ Implicit computation complexity in higher-order programming languages

Cites Work

• Automatic synthesis of typed \(\Lambda\)-programs on term algebras
• The realm of primitive recursion
• Finitely stratified polymorphism
• A new recursion-theoretic characterization of the polytime functions
• The typed lambda-calculus is not elementary recursive
• A foundational delineation of poly-time
• A characterization of alternating log time by ramified recurrence
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
• Classes of Predictably Computable Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity