Please use this identifier to cite or link to this item:
|Title:||Computable categoricity and the Ershov hierarchy||Authors:||Khoussainov, B.
Graphs with finite components
|Issue Date:||Nov-2008||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||URI:||http://scholarbank.nus.edu.sg/handle/10635/103019||ISSN:||01680072||DOI:||10.1016/j.apal.2008.06.010|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.