Polynomial-time abelian groups

Annals of Pure and Applied Logic 56 (1-3):313-363 (1992)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 84,213

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

Space complexity of Abelian groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.
The model theory of finitely generated finite-by-Abelian groups.Francis Oger - 1984 - Journal of Symbolic Logic 49 (4):1115-1124.
Polynomial-time versus recursive models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.
Some model theory of Abelian groups.Paul C. Eklof - 1972 - Journal of Symbolic Logic 37 (2):335-342.
Axiomatization of abelian-by- G groups for a finite group G.Francis Oger - 2001 - Archive for Mathematical Logic 40 (7):515-521.
P-compatible Abelian groups.Krystyna Mruczek-Nasieniewska - 2005 - Logic and Logical Philosophy 14 (2):253-263.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.


Added to PP

16 (#705,478)

6 months
1 (#508,356)

Historical graph of downloads
How can I increase my downloads?