Degree spectra of the successor relation of computable linear orderings

DOI10.1007/S00153-008-0110-6zbMath1161.03022OpenAlexW2019414989MaRDI QIDQ1005920

J. Martínez

Publication date: 17 March 2009

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-008-0110-6

zbMATH Keywords

degree spectrumcomputable linear orderingsuccessor relationcomputably enumerable Turing degreeupper cone

Mathematics Subject Classification ID

Total orders (06A05) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items (8)

Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders ⋮ Punctual 1-linear orders ⋮ Presentations of the successor relation of computable linear ordering ⋮ Corrigendum: "On the complexity of the successivity relation in computable linear orderings" ⋮ Computable linear orders and the Ershov hierarchy ⋮ Computable linear orders and limitwise monotonic functions ⋮ ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS ⋮ Computable linear orders and the ershov hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Autostability of models
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• Classical recursion theory. The theory of functions and sets of natural numbers
• Every recursive Boolean algebra is isomorphic to one with incomplete atoms
• Computable structures and the hyperarithmetical hierarchy
• Recursive isomorphism types of recursive Boolean algebras
• Recursively Categorical Linear Orderings
• Recursive Linear Orders with Incomplete Successivities

This page was built for publication: Degree spectra of the successor relation of computable linear orderings