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

Hardy functionalshierarchynested recursionsrecursive and iterative definitions of total computable functionsstructured tree-ordinalssubrecursion

Mathematics Subject Classification ID

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

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

• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• 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?)
• Nested recursion
• Rapidly growing Ramsey functions
• Slow growing versus fast growing

Cited in

(16)

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

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)