Computable categoricity of graphs with finite components
| aut.researcher | Liu, Jiamou | |
| dc.contributor.author | Csima, B | |
| dc.contributor.author | Khoussainov, B | |
| dc.contributor.author | Liu, J | |
| dc.contributor.editor | Beckmann, A | |
| dc.contributor.editor | Dimitracopoulos, C | |
| dc.contributor.editor | Löwe, L | |
| dc.date.accessioned | 2011-11-27T03:47:01Z | |
| dc.date.available | 2011-11-27T03:47:01Z | |
| dc.date.copyright | 2008-06 | |
| dc.date.issued | 2008-06 | |
| dc.description.abstract | A computable graph is computably categorical if any two computable presentations of the graph are computably isomorphic. In this paper we investigate the class of computably categorical graphs. We restrict ourselves to strongly locally finite graphs; these are the graphs all of whose components are finite. We present a necessary and sufficient condition for certain classes of strongly locally finite graphs to be computably categorical. We prove that if there exists an infinite \Delta^0_2-set of components that can be properly embedded into infinitely many components of the graph then the graph is not computably categorical. We outline the construction of a strongly locally finite computably categorical graph with an infinite chain of properly embedded components. | |
| dc.format.medium | paper and online | |
| dc.identifier.citation | Computer Science: Logic and Theory of Algorithms, Lecture Notes in Computer Science: proceedings from the 4th Conference on Computability in Europe (CiE'08), Athens, Greece, vol.5028, pages 139 - 148 | |
| dc.identifier.doi | 10.1007/978-3-540-69407-6_15 | |
| dc.identifier.isbn | 978-3-540-69405-2 | |
| dc.identifier.issn | 0302-9743 (Print) 1611-3349 (Online | |
| dc.identifier.uri | https://hdl.handle.net/10292/2811 | |
| dc.publisher | Springer Berlin / Heidelberg | |
| dc.relation.uri | http://dx.doi.org/10.1007/978-3-540-69407-6_15 | |
| dc.rights | An author may self-archive an author-created version of his/her article on his/her own website and or in his/her institutional repository. He/she may also deposit this version on his/her funder’s or funder’s designated repository at the funder’s request or as a result of a legal obligation, provided it is not made publicly available until 12 months after official publication. He/ she may not use the publisher's PDF version, which is posted on www.springerlink.com, for the purpose of self-archiving or deposit. Furthermore, the author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at www.springerlink.com”. (Please also see Publisher’s Version and Citation) | |
| dc.rights.accessrights | OpenAccess | |
| dc.title | Computable categoricity of graphs with finite components | |
| dc.type | Conference Contribution | |
| pubs.organisational-data | /AUT | |
| pubs.organisational-data | /AUT/Design & Creative Technologies | |
| pubs.organisational-data | /AUT/Design & Creative Technologies/School of Computing & Mathematical Science | |
| pubs.organisational-data | /AUT/PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers/DCT C & M Computing |