Please use this identifier to cite or link to this item:
Title: Computable categoricity and the Ershov hierarchy
Authors: Khoussainov, B.
Stephan, F. 
Yang, Y. 
Keywords: Categoricity
Ershov hierarchy
Graphs with finite components
Model theory
Recursion theory
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.
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
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.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.