Computable Isomorphisms for Certain Classes of Infinite Graphs

DOI10.1142/S0218216518410122MaRDI QIDQ6281589arXivWikidataFDO

Authors Hakim J. Walker

Publication date 5 January 2017

Mathematics Subject Classification ID

Infinite graphs (05C63) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Abstract: We investigate (2,1):1 structures, which consist of a countable set $A$ together with a function $f:AoA$ such that for every element $x$ in $A$, $f$ maps either exactly one element or exactly two elements of $A$ to $x$. These structures extend the notions of injection structures, 2:1 structures, and (2,0):1 structures studied by Cenzer, Harizanov, and Remmel, all of which can be thought of as infinite directed graphs. We look at various computability-theoretic properties of (2,1):1 structures, most notably that of computable categoricity. We say that a structure $mathcalA$ is computably categorical if there exists a computable isomorphism between any two computable copies of $mathcalA$. We give a sufficient condition under which a (2,1):1 structure is computably categorical, and present some examples of (2,1):1 structures with different computability-theoretic properties.

This page was built for publication: Computable Isomorphisms for Certain Classes of Infinite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281589)