Codings on linear orders and algorithmic independence of natural relations

DOI10.1134/S1995080214040131zbMATH Open1325.03052MaRDI QIDQ2263111FDOQ2263111

Authors: R. I. Bikmukhametov 

Publication date: 17 March 2015

Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 1873432
• A coding of the countable linear orderings
• Relative complexity for computable presentations of the conventional linear order on the set of naturals
• Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders
• scientific article; zbMATH DE number 1303201
• Computability-theoretic and proof-theoretic aspects of partial and linear orderings
• Linearization of definable order relations
• On the complexity of the successivity relation in computable linear orderings
• The block relation in computable linear orders
• On self-embeddings of computable linear orderings

zbMATH Keywords

block relationdensity relationleft limit relationlinear orderright limit relationcodingcomputable presentationneighborhood relationalgorithmic independence

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Recursively Categorical Linear Orderings
• Recursive linear orders with recursive successivities
• Computability on linear orderings enriched with predicates
• Initial segments of computable linear orders with additional computable predicates
• Every Low 2 Boolean Algebra has a Recursive Copy
• A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
• Title not available (Why is that?)
• Δ 2 0 -copies of linear orderings
• On the complexity of the successivity relation in computable linear orderings
• Low linear orderings

Cited In (8)

• Relative complexity for computable presentations of the conventional linear order on the set of naturals
• Initial segments of computable linear orders with computable natural relations
• Computable linear orders and the Ershov hierarchy
• Computable linear orders and the ershov hierarchy
• Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders
• CODING IN GRAPHS AND LINEAR ORDERINGS
• A coding of the countable linear orderings
• Cuts of linear orders

This page was built for publication: Codings on linear orders and algorithmic independence of natural relations

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