Subrecursion and lambda representation over free algebras. Preliminary summary

MaRDI QIDQ4035315zbMATH OpenFDO

Authors Daniel M. Leivant

Publication date 18 May 1993

zbMATH Keywords

\(\lambda\)-calculuscomputing over general algebraic structuressubrecurrence over free algebrassubrecursive hierarchytiered recurrence

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Recursive functions and relations, subrecursive hierarchies (03D20) Applications of computability and recursion theory (03D80) Symbolic computation and algebraic computation (68W30)

Recommendations

• Functions over free algebras definable in the simply typed lambda calculus
• Some Hierarchies of Primitive Recursive Functions on Term Algebras
• Lambda-representable functions over term algebras
• \(\lambda\)-definability of free algebras
• scientific article; zbMATH DE number 149520

Cited in

(16)

• Implicit characterizations of FPTIME and NC revisited
• A new recursion-theoretic characterization of the polytime functions
• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• Ordinals and ordinal functions representable in the simply typed lambda calculus
• Functions over free algebras definable in the simply typed lambda calculus
• Function-algebraic characterizations of log and polylog parallel time
• Higher type recursion, ramification and polynomial time
• On the computational complexity of imperative programming languages
• A characterization of alternating log time by ramified recurrence
• Feasible functionals and intersection of ramified types
• Letterplace
• Lambda-representable functions over term algebras
• On parallel hierarchies and R ki
• Intrinsic theories and computational complexity
• Characterizing parallel time by type 2 recursions with polynomial output length
• \(\lambda\)-definability of free algebras

This page was built for publication: Subrecursion and lambda representation over free algebras. Preliminary summary

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