Recursive Structures and Ershov's Hierarchy

DOI10.1002/MALQ.19960420138MaRDI QIDQ5687409zbMATH OpenOpenAlexFDO

Authors C. J. Ash, J. F. Knight

Publication date 27 May 1997

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19960420138

zbMATH Keywords

difference hierarchyErshov's hierarchyintrinsically \(\alpha\)-r.e.intrinsically r.e. relationsrecursive structures

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Hierarchies of computability and definability (03D55)

Recommendations

• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Definable relations in Turing degree structures
• Definability and elementary equivalence in the Ershov difference hierarchy
• The Ershov hierarchy
• Turing degrees and the Ershov hierarchy

Cited in

(18)

• Stability of recursive structures in arithmetical degrees
• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Turing degrees of certain isomorphic images of computable relations
• Deriving structural hylomorphisms from recursive definitions
• Rice and Rice-Shapiro theorems for transfinite correction grammars
• Program size complexity of correction grammars in the Ershov hierarchy
• scientific article; zbMATH DE number 5485222 (Why is no real title available?)
• Learning correction grammars
• scientific article; zbMATH DE number 3920456 (Why is no real title available?)
• Recursive properties of branching and BGG resolution
• scientific article; zbMATH DE number 1302872 (Why is no real title available?)
• A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas
• Degree spectra of relations on a cone
• scientific article; zbMATH DE number 874495 (Why is no real title available?)
• Ranked structures and arithmetic transfinite recursion
• The Complexity of intrinsically r.e. subsets of existentially decidable models
• Resource restricted computability theoretic learning: Illustrative topics and problems
• The Hausdorff-Ershov hierarchy in Euclidean spaces

This page was built for publication: Recursive Structures and Ershov's Hierarchy

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