Some effects of Ash-Nerode and other decidability conditions on degree spectra

DOI10.1016/0168-0072(91)90097-6zbMath0756.03022OpenAlexW1975720205MaRDI QIDQ1182431

Valentina S. Harizanov

Publication date: 28 June 1992

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(91)90097-6

zbMATH Keywords

recursive modelAsh-Nerode decidability conditiondegree spectrum of a relation

Mathematics Subject Classification ID

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

Related Items (21)

Possible degrees in recursive copies ⋮ Π₁¹ relations and paths through ⋮ Quasi-simple relations in copies of a given recursive structure ⋮ Permitting, forcing, and copying of a given recursive relation ⋮ Possible degrees in recursive copies. II ⋮ Freely generated projective planes with finite computable dimension ⋮ Turing degrees of hypersimple relations on computable structures ⋮ Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures ⋮ Degree Spectra of Relations on a Cone ⋮ DEGREES OF CATEGORICITY ON A CONE VIAη-SYSTEMS ⋮ The possible Turing degree of the nonzero member in a two element degree spectrum ⋮ Π₁⁰ classes and strong degree spectra of relations ⋮ The theory of projective planes is complete with respect to degree spectra and effective dimensions ⋮ Degree spectra of the successor relation of computable linear orderings ⋮ ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS ⋮ Turing degrees of certain isomorphic images of computable relations ⋮ Computable isomorphisms, degree spectra of relations, and Scott families ⋮ Coding a family of sets ⋮ Degree Spectra of Relations on Computable Structures ⋮ Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms ⋮ Generalised weak presentations

Cites Work

• Computable single-valued numerations
• Uncountable degree spectra
• Autostability and computable families of constructivizations
• Foundations of recursive model theory
• Semirecursive Sets and Positive Reducibility
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some effects of Ash-Nerode and other decidability conditions on degree spectra