Computable Categoricity and the Ershov Hierarchy
| dc.contributor.author | KHOUSSAINOV, Bakhadyr | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.contributor.author | YANG, Yue | en_US |
| dc.date.accessioned | 2007-10-23T01:48:00Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:28Z | |
| dc.date.available | 2007-10-23T01:48:00Z | en_US |
| dc.date.available | 2017-01-23T07:00:28Z | |
| dc.date.issued | 2007-08-31 | en_US |
| dc.description.abstract | In this paper, the notions of F[alpha]-categorical and G[alpha]-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the alpha-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 G[2]-categorical; in the latter case it is not F[alpha]-categorical for any recursive ordinal alpha. | en_US |
| dc.format.extent | 520439 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2578 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRD8/07 | en_US |
| dc.title | Computable Categoricity and the Ershov Hierarchy | en_US |
| dc.type | Technical Report | en_US |