Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.tcs.2015.11.042
Title: | Reducibilities among equivalence relations induced by recursively enumerable structures | Authors: | Gavryushkin A. Khoussainov B. Stephan F. |
Keywords: | Algebraic structures Degrees Realisability Recursively enumerable equivalence classes Reducibilities |
Issue Date: | 2016 | Publisher: | Elsevier | Citation: | Gavryushkin A., Khoussainov B., Stephan F. (2016). Reducibilities among equivalence relations induced by recursively enumerable structures. Theoretical Computer Science 612 : 137-152. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2015.11.042 | Abstract: | In this paper we investigate the dependence of recursively enumerable structures on the equality relation which is fixed to a specific r.e. equivalence relation. We compare r.e. equivalence relations on the natural numbers with respect to the amount of structures they permit to represent from a given class of structures such as algebras, permutations and linear orders. In particular, we show that for various types of structures represented, there are minimal and maximal elements. © 2015 Elsevier B.V. | Source Title: | Theoretical Computer Science | URI: | https://scholarbank.nus.edu.sg/handle/10635/177537 | ISSN: | 0304-3975 | DOI: | 10.1016/j.tcs.2015.11.042 |
Appears in Collections: | Staff Publications Elements |
Show full item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
gks.pdf | 282.71 kB | Adobe PDF | OPEN | Post-print | View/Download |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.