Please use this identifier to cite or link to this item:
|Title:||Computable categoricity and the Ershov hierarchy|
Graphs with finite components
|Citation:||Khoussainov, B., Stephan, F., Yang, Y. (2008-11). Computable categoricity and the Ershov hierarchy. Annals of Pure and Applied Logic 156 (1) : 86-95. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2008.06.010|
|Abstract:||In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for any recursive ordinal α. © 2008 Elsevier B.V. All rights reserved.|
|Source Title:||Annals of Pure and Applied Logic|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 15, 2018
WEB OF SCIENCETM
checked on May 8, 2018
checked on May 11, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.