Switch to: References

Add citations

You must login to add citations.
  1. Graphs realised by r.e. equivalence relations.Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan - 2014 - Annals of Pure and Applied Logic 165 (7-8):1263-1290.
    We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.
    We study the notion of polynomial-time relation reducibility among computable equivalence relations. We identify some benchmark equivalence relations and show that the reducibility hierarchy has a rich structure. Specifically, we embed the partial order of all polynomial-time computable sets into the polynomial-time relation reducibility hierarchy between two benchmark equivalence relations Eλ and id. In addition, we consider equivalence relations with finitely many nontrivial equivalence classes and those whose equivalence classes are all finite.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark