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

Abstract
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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(92)90076-c
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,959
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Polynomial-Time Versus Recursive Models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.

Add more references

Citations of this work BETA

Space Complexity of Abelian Groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.

View all 9 citations / Add more citations

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.

Analytics

Added to PP index
2014-01-16

Total views
15 ( #697,362 of 2,504,817 )

Recent downloads (6 months)
1 ( #417,030 of 2,504,817 )

How can I increase my downloads?

Downloads

My notes