Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.apal.2014.04.001
Title: Graphs realised by r.e. equivalence relations
Authors: Gavruskin, A.
Jain, S. 
Khoussainov, B.
Stephan, F. 
Keywords: C-reducibility
M-reducibility
Recursively enumerable equivalence relation
Recursively enumerable structure
Issue Date: 2014
Citation: Gavruskin, A., Jain, S., Khoussainov, B., Stephan, F. (2014). Graphs realised by r.e. equivalence relations. Annals of Pure and Applied Logic 165 (7-8) : 1263-1290. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2014.04.001
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. © 2014 Elsevier B.V.
Source Title: Annals of Pure and Applied Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/113921
ISSN: 01680072
DOI: 10.1016/j.apal.2014.04.001
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

7
checked on Dec 13, 2018

WEB OF SCIENCETM
Citations

3
checked on Dec 13, 2018

Page view(s)

38
checked on Nov 23, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.