Ordinal complexity of recursive definitions

DOI10.1016/0890-5401(92)90027-DMaRDI QIDQ1193596zbMATH OpenOpenAlexFDO

Authors M. V. H. Fairtlough, Stanley S. Wainer

Publication date 27 September 1992

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(92)90027-d

zbMATH Keywords

hierarchyHardy functionalsnested recursionsrecursive and iterative definitions of total computable functionsstructured tree-ordinalssubrecursion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• Recursion on generalized computable ordinals
• Turing complexity of the ordinals
• scientific article; zbMATH DE number 1390019
• Ordinal recursive complexity of unordered data nets
• DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY
• The recursion-theoretic structure of complexity classes
• scientific article; zbMATH DE number 3885307
• scientific article; zbMATH DE number 4108743
• A characterization of the complexity of recursive predicates
• scientific article; zbMATH DE number 4037837

Cites work

• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 3920456 (Why is no real title available?)
• scientific article; zbMATH DE number 4033742 (Why is no real title available?)
• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• Nested recursion
• Rapidly growing Ramsey functions
• Slow growing versus fast growing

Cited in

(15)

• Accessible Recursive Functions
• scientific article; zbMATH DE number 218515 (Why is no real title available?)
• Iterated inductive definitions revisited
• Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones
• An ordinal calculus for proving termination in term rewriting
• Transfinite induction within Peano arithmetic
• Walther recursion
• The hierarchy of terminating recursive programs over N
• Ordinal recursive bounds for Higman's theorem
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• From hierarchies to well-foundedness
• Optimal bounds for ordinal comparison maps
• Partitioning 𝛼–large sets: Some lower bounds
• Complexity hierarchies beyond elementary
• A difference in complexity between recursion and tail recursion

This page was built for publication: Ordinal complexity of recursive definitions

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