Graphs realised by r.e. equivalence relations

DOI10.1016/j.apal.2014.04.001zbMath1351.03028OpenAlexW2005704285MaRDI QIDQ2349100

Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan, Aleksandr Nikolaevich Gavryushkin

Publication date: 17 June 2015

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

Full work available at URL: https://doi.org/10.1016/j.apal.2014.04.001

zbMATH Keywords

\(m\)-reducibility\(C\)-reducibilityrecursively enumerable equivalence relationrecursively enumerable structure

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Recursive equivalence types of sets and structures, isols (03D50) Theory of numerations, effectively presented structures (03D45)

Related Items

LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS ⋮ Boolean algebras realized by c.e. equivalence relations ⋮ Uniformly computably separable algebras with effectively splittable families of negative congruences ⋮ INITIAL SEGMENTS OF THE DEGREES OF CEERS ⋮ The theory of ceers computes true arithmetic ⋮ Word problems and ceers ⋮ ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS ⋮ Reducibilities among equivalence relations induced by recursively enumerable structures ⋮ Classifying word problems of finitely generated algebras via computable reducibility ⋮ Classifying equivalence relations in the Ershov hierarchy ⋮ A Survey on Universal Computably Enumerable Equivalence Relations ⋮ THE COMPLEXITY OF INDEX SETS OF CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS ⋮ Learnability and positive equivalence relations ⋮ On computably enumerable structures ⋮ Learnability and positive equivalence relations ⋮ Well-orders realized by C.E. equivalence relations ⋮ EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinite time decidable equivalence relation theory
• The effective theory of Borel equivalence relations
• Reducibilities among equivalence relations induced by recursively enumerable structures
• On the relation provable equivalence and on partitions in effectively inseparable sets
• Relatively precomplete numerations and arithmetic
• Classical recursion theory. The theory of functions and sets of natural numbers
• Initial segments of recursive linear orders
• Positive equivalences
• Quantifying the amount of verboseness
• Recursion theoretic properties of frequency computation and bounded queries
• UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• A Note on Positive Equivalence Relations
• Strong isomorphism reductions in complexity theory
• On Σ¹ ₁ equivalence relations over the natural numbers
• Classifying positive equivalence relations
• Equivalence Relations on Classes of Computable Structures
• Rekursive Algebren mit Kettenbedingungen
• The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
• COMPUTABLY ENUMERABLE ALGEBRAS, THEIR EXPANSIONS, AND ISOMORPHISMS
• Isomorphism relations on computable structures
• Semirecursive Sets and Positive Reducibility
• Recursively enumerable sets of positive integers and their decision problems
• Computably enumerable equivalence relations