On the complexity of the successivity relation in computable linear orderings
From MaRDI portal
Publication:3094355
DOI10.1142/S0219061310000924zbMATH Open1256.03039MaRDI QIDQ3094355FDOQ3094355
Authors: Steffen Lempp, Rodney G. Downey, Guohua Wu 
Publication date: 24 October 2011
Published in: Journal of Mathematical Logic (Search for Journal in Brave)
Recommendations
- Presentations of the successor relation of computable linear ordering
- Degree spectra of the successor relation of computable linear orderings
- A note on \(\Delta_2^0\)-spectra of linear orderings and degree spectra of the successor relation
- Δ 2 0 -copies of linear orderings
- Computable linear orders and the Ershov hierarchy
Computable structure theory, computable model theory (03C57) Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45)
Cites Work
- Computable structures and the hyperarithmetical hierarchy
- Every recursive Boolean algebra is isomorphic to one with incomplete atoms
- A construction for recursive linear orderings
- Degree spectra and computable dimensions in algebraic structures
- Degrees coded in jumps of orderings
- Degrees of orderings not isomorphic to recursive linear orderings
- Degree spectra of the successor relation of computable linear orderings
- The \(\Delta_2^0\)-spectrum of a linear order
- Degree Spectra of Relations on Computable Structures
- 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
- Relations Intrinsically Recursive in Linear Orders
- On computable self-embeddings of computable linear orderings
Cited In (13)
- Some Questions in Computable Mathematics
- Codings on linear orders and algorithmic independence of natural relations
- COMPUTABILITY AND UNCOUNTABLE LINEAR ORDERS II: DEGREE SPECTRA
- Computable linear orders and limitwise monotonic functions
- Recursive linear orders with recursive successivities
- Presentations of the successor relation of computable linear ordering
- Degree spectra of the successor relation of computable linear orderings
- Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders
- Recursive Linear Orders with Incomplete Successivities
- The complexity space of a valued linearly ordered set
- Corrigendum: "On the complexity of the successivity relation in computable linear orderings"
- Spectral universality of linear orders with one binary relation
- A note on \(\Delta_2^0\)-spectra of linear orderings and degree spectra of the successor relation
This page was built for publication: On the complexity of the successivity relation in computable linear orderings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094355)
