Computability on linear orderings enriched with predicates

DOI10.1007/s10469-009-9067-8zbMath1241.03055OpenAlexW2088657950MaRDI QIDQ431704

J. Herrera, H. S. Yoon

Publication date: 29 June 2012

Published in: Algebra and Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10469-009-9067-8

zbMATH Keywords

computabilityquasidiscrete linear ordering

Mathematics Subject Classification ID

Total orders (06A05) Theory of numerations, effectively presented structures (03D45)

Related Items (14)

Initial segments of computable linear orders with computable natural relations ⋮ Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders ⋮ A computably enumerable partial ordering without computably enumerable maximal chains and antichains ⋮ THE SIMPLEST LOW LINEAR ORDER WITH NO COMPUTABLE COPIES ⋮ Cuts of linear orders ⋮ COMPUTABLE LINEAR ORDERS AND PRODUCTS ⋮ On a computable presentation of low linear orderings ⋮ Computable linear orders and the Ershov hierarchy ⋮ Scattered linear orderings with no computable presentation ⋮ Codings on linear orders and algorithmic independence of natural relations ⋮ Computable linear orders and limitwise monotonic functions ⋮ Degree spectra of structures ⋮ Computable presentability of countable linear orders ⋮ Computable linear orders and the ershov hierarchy

Cites Work

• Computable Boolean algebras
• Jumps of Orderings
• A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
• A construction for recursive linear orderings
• Every Low Boolean Algebra is Isomorphic to a Recursive One
• Every Low 2 Boolean Algebra has a Recursive Copy
• Δ 2 0 -copies of linear orderings
• Hierarchies of Boolean algebras

This page was built for publication: Computability on linear orderings enriched with predicates