We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...) example, we give conditions are given under which two isomorphic LOGSPACE structures will have a linear space isomorphism. (shrink)

Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given (...) class in a way that is effective enough to preserve the property in which we are interested. In this paper, we show how to transfer a number of computability-theoretic properties from directed graphs to structures in the following classes: symmetric, irreflexive graphs; partial orderings; lattices; rings ; integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups. This allows us to show that several theorems about degree spectra of relations on computable structures, nonpreservation of computable categoricity, and degree spectra of structures remain true when we restrict our attention to structures in any of the classes on this list. The codings we present are general enough to be viewed as establishing that the theories mentioned above are computably complete in the sense that, for a wide range of computability-theoretic nonstructure type properties, if there are any examples of structures with such properties then there are such examples that are models of each of these theories. (shrink)

This paper is a continuation of the authors' work , where the main problem considered was whether a given recursive structure is recursively isomorphic to a polynomial-time structure. In that paper, a recursive Abelian group was constructed which is not recursively isomorphic to any polynomial-time Abelian group. We now show that if every element of a recursive Abelian group has finite order, then the group is recursively isomorphic to a polynomial-time group. Furthermore, if the orders are bounded, then the group (...) is recursively isomorphic to a polynomial-time group with universe A being the set of tally representations of natural numbers Tal = s{;1s};* or the set of binary representations of the natural numbers Bin. We also construct a recursive Abelian group with all elements of finite order but which has elements of arbitrary large finite order which is not isomorphic to any polynomial-time group with universe Tal or Bin. Similar results are obtained for structures , where f is a permutation on the set A. (shrink)