ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS

DOI10.1142/S0219061310000924zbMath1256.03039MaRDI QIDQ3094355

Steffen Lempp, Rodney G. Downey, Guohua Wu

Publication date: 24 October 2011

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

zbMATH Keywords

computable linear orderingspectra of relationssuccessivity

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items (6)

Corrigendum: "On the complexity of the successivity relation in computable linear orderings" ⋮ Some Questions in Computable Mathematics ⋮ A note on \(\Delta_2^0\)-spectra of linear orderings and degree spectra of the successor relation ⋮ Codings on linear orders and algorithmic independence of natural relations ⋮ Computable linear orders and limitwise monotonic functions ⋮ COMPUTABILITY AND UNCOUNTABLE LINEAR ORDERS II: DEGREE SPECTRA

Cites Work

• Degrees of orderings not isomorphic to recursive linear orderings
• Degree spectra of the successor relation of computable linear orderings
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• Uncountable degree spectra
• The possible Turing degree of the nonzero member in a two element degree spectrum
• Every recursive Boolean algebra is isomorphic to one with incomplete atoms
• Computable structures and the hyperarithmetical hierarchy
• Degree spectra and computable dimensions in algebraic structures
• The -spectrum of a linear order
• On computable self-embeddings of computable linear orderings
• Relations Intrinsically Recursive in Linear Orders
• Degrees coded in jumps of orderings
• A construction for recursive linear orderings
• Degree Spectra of Relations on Computable Structures

This page was built for publication: ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS