Reducibilities among equivalence relations induced by recursively enumerable structures

DOI10.1016/j.tcs.2015.11.042zbMath1338.03077OpenAlexW2181593437WikidataQ59864164 ScholiaQ59864164MaRDI QIDQ896924

Alex Gavryushkin, Frank Stephan, Bakhadyr Khoussainov

Publication date: 15 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.11.042

zbMATH Keywords

realizabilitydegreesalgebraic structuresreducibilitiesrecursively enumerable equivalence relations

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (18)

On dark computably enumerable equivalence relations ⋮ Index sets for classes of positive preorders ⋮ 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 ⋮ ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS ⋮ Classifying word problems of finitely generated algebras via computable reducibility ⋮ On the main scientific achievements of Victor Selivanov ⋮ 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 ⋮ Positive preorders ⋮ On computably enumerable structures ⋮ Learnability and positive equivalence relations ⋮ Well-orders realized by C.E. equivalence relations ⋮ Graphs realised by r.e. equivalence relations ⋮ EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS ⋮ Subrecursive equivalence relations and (non-)closure under lattice operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinite time decidable equivalence relation theory
• The effective theory of Borel equivalence relations
• On the relation provable equivalence and on partitions in effectively inseparable sets
• 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
• Finitely presented expansions of computably enumerable semigroups
• Graphs realised by r.e. equivalence relations
• A Note on Positive Equivalence Relations
• Strong isomorphism reductions in complexity theory
• On Σ¹ ₁ equivalence relations over the natural numbers
• LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS
• 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
• Computably enumerable equivalence relations

This page was built for publication: Reducibilities among equivalence relations induced by recursively enumerable structures