首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Graphs realised by r.e. equivalence relations
Institution:1. Department of Computer Science, The University of Auckland, New Zealand;2. School of Computing, National University of Singapore, Singapore 117417, Republic of Singapore;3. Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore 119076, Republic of Singapore
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.
Keywords:Recursively enumerable equivalence relation  Recursively enumerable structure
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号