Space complexity of Abelian groups

Archive for Mathematical Logic 48 (1):115-140 (2009)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 91,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
$$\Pi^0_1$$ -Presentations of Algebras.Bakhadyr Khoussainov, Theodore Slaman & Pavel Semukhin - 2006 - Archive for Mathematical Logic 45 (6):769-781.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
The model theory of finitely generated finite-by-Abelian groups.Francis Oger - 1984 - Journal of Symbolic Logic 49 (4):1115-1124.
Some model theory of Abelian groups.Paul C. Eklof - 1972 - Journal of Symbolic Logic 37 (2):335-342.
The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups.Philip Scowcroft - 2007 - Notre Dame Journal of Formal Logic 48 (4):521-550.
On the computational complexity of the theory of Abelian groups.Libo Lo - 1988 - Annals of Pure and Applied Logic 37 (3):205-248.


Added to PP

72 (#216,970)

6 months
9 (#210,105)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Polynomial-time abelian groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Polynomial-time versus recursive models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.
Complexity-theoretic algebra II: Boolean algebras.A. Nerode & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 44 (1-2):71-99.

Add more references