Reducibilities among equivalence relations induced by recursively enumerable structures

DOI10.1016/J.TCS.2015.11.042zbMATH Open1338.03077OpenAlexW2181593437WikidataQ59864164 ScholiaQ59864164MaRDI QIDQ896924FDOQ896924

Authors: Alex Gavryushkin, Bakhadyr Khoussainov, Frank Stephan 

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

Recommendations

• Graphs realised by r.e. equivalence relations
• Linear orders realized by c.e. equivalence relations
• scientific article; zbMATH DE number 4116518
• On recursively enumerable structures
• On the degree structure of equivalence relations under computable reducibility

zbMATH Keywords

realizabilityalgebraic structuresdegreesreducibilitiesrecursively enumerable equivalence relations

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On Σ¹ ₁ equivalence relations over the natural numbers
• Isomorphism relations on computable structures
• Semirecursive Sets and Positive Reducibility
• A Note on Positive Equivalence Relations
• Graphs realised by r.e. equivalence relations
• The effective theory of Borel equivalence relations
• Classical recursion theory. The theory of functions and sets of natural numbers
• Rekursive Algebren mit Kettenbedingungen
• Initial segments of recursive linear orders
• Infinite time decidable equivalence relation theory
• Positive equivalences
• Classifying positive equivalence relations
• Computably enumerable equivalence relations
• Strong isomorphism reductions in complexity theory
• On the relation provable equivalence and on partitions in effectively inseparable sets
• Recursion theoretic properties of frequency computation and bounded queries
• Quantifying the amount of verboseness
• Finitely presented expansions of computably enumerable semigroups
• Linear orders realized by c.e. equivalence relations
• Equivalence Relations on Classes of Computable Structures
• Title not available (Why is that?)
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Title not available (Why is that?)
• COMPUTABLY ENUMERABLE ALGEBRAS, THEIR EXPANSIONS, AND ISOMORPHISMS

Cited In (32)

• Well-orders realized by C.E. equivalence relations
• Positive preorders
• On the main scientific achievements of Victor Selivanov
• Subrecursive equivalence relations and (non-)closure under lattice operations
• Boolean algebras realized by c.e. equivalence relations
• Learnability and positive equivalence relations
• Comparing Classes of Finite Structures
• Universal recursion theoretic properties of r.e. preordered structures
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• Combinatorics of reductions between equivalence relations
• Calculable enumerations and equivalence relations
• Initial segments of the degrees of ceers
• Title not available (Why is that?)
• On isomorphism classes of computably enumerable equivalence relations
• On dark computably enumerable equivalence relations
• A survey on universal computably enumerable equivalence relations
• On recursively enumerable structures
• Measuring the complexity of reductions between equivalence relations
• EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS
• Index sets for classes of positive preorders
• The complexity of index sets of classes of computably enumerable equivalence relations
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• Uniformly computably separable algebras with effectively splittable families of negative congruences
• On computably enumerable structures
• Learnability and positive equivalence relations
• Classifying word problems of finitely generated algebras via computable reducibility
• Linear orders realized by c.e. equivalence relations
• Reducibility of equivalence relations arising from nonstationary ideals under large cardinal assumptions
• On learning down-sets in quasi-orders, and ideals in Boolean algebras
• Title not available (Why is that?)
• Graphs realised by r.e. equivalence relations
• On the degree structure of equivalence relations under computable reducibility

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

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