Abstract | ||
---|---|---|
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 types of some of these partial orders. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1016/j.apal.2014.04.001 | Annals of Pure and Applied Logic |
Keywords | Field | DocType |
03D25,03D30,03D45,03D50 | Graph,Discrete mathematics,Equivalence relation,Combinatorics,Maximal set,Recursively enumerable set,Recursively enumerable language,Isomorphism,Maximal element,Mathematics,Partially ordered set | Journal |
Volume | Issue | ISSN |
165 | 7 | 0168-0072 |
Citations | PageRank | References |
6 | 0.65 | 15 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alexander Gavruskin | 1 | 9 | 2.13 |
Sanjay Jain | 2 | 1647 | 177.87 |
Bakhadyr Khoussainov | 3 | 604 | 72.96 |
Frank Stephan | 4 | 329 | 34.02 |