Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435470 | Theoretical Computer Science | 2016 | 16 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alex Gavryushkin, Bakhadyr Khoussainov, Frank Stephan,