Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.apal.2008.06.010
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. 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.

SCOPUSTM   
Citations

5
checked on May 15, 2018

WEB OF SCIENCETM
Citations

6
checked on May 8, 2018

Page view(s)

38
checked on May 11, 2018

Google ScholarTM

Check

Altmetric


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