David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 41 (3):561-573 (1976)
Mostowski  shows that if a structure has a decidable theory, then its weak direct power has one as well; his proof however never produces decision procedures which are elementary recursive. Some very general results are obtained here about the nature of the weak direct power of a structure, which in most cases lead to elementary recursive decision procedures for weak direct powers of structures which themselves have elementary recursive procedures. In particular, it is shown that $\langle N^\ast, +\rangle$ , the weak direct power of $\langle N, +\rangle$ , can be decided in space 2 2 2 cn for some constant c. As corollaries, the same upper bound is obtained for the theory of the structure $\langle N^+, \cdot\rangle$ of positive integers under multiplication, and for the theory of finite abelian groups. Fischer and Rabin  have shown that the theory of $\langle N^\ast, +\rangle$ requires time 2 2 2 dn even on nondeterministic Turing machines
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
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
No references found.
Citations of this work BETA
Kevin J. Compton & C. Ward Henson (1990). A Uniform Method for Proving Lower Bounds on the Computational Complexity of Logical Theories. Annals of Pure and Applied Logic 48 (1):1-79.
Libo Lo (1988). On the Computational Complexity of the Theory of Abelian Groups. Annals of Pure and Applied Logic 37 (3):205-248.
Similar books and articles
Alexis Bés & Denis Richard (1998). Undecidable Extensions of Skolem Arithmetic. Journal of Symbolic Logic 63 (2):379-401.
Keith Frankish (2007). Deciding to Believe Again. Mind 116 (463):523 - 547.
I. Sh Kalimullin (2002). Splitting Properties of N-C.E. Enumeration Degrees. Journal of Symbolic Logic 67 (2):537-546.
Kenneth L. Manders (1979). The Theory of All Substructures of a Structure: Characterisation and Decision Problems. Journal of Symbolic Logic 44 (4):583-598.
Rami Grossberg (1988). A Downward Löwenheim-Skolem Theorem for Infinitary Theories Which Have the Unsuperstability Property. Journal of Symbolic Logic 53 (1):231-242.
Alexis Bès (1997). Undecidable Extensions of Büchi Arithmetic and Cobham-Semënov Theorem. Journal of Symbolic Logic 62 (4):1280-1296.
Ya'acov Peterzil (1993). Reducts of Some Structures Over the Reals. Journal of Symbolic Logic 58 (3):955-966.
Patrick Simonetta (1998). Equivalence Elementaire Et Decidabilite Pour Des Structures du Type Groupe Agissant Sur Un Groupe Abelien. Journal of Symbolic Logic 63 (4):1255-1285.
P. T. Bateman, C. G. Jockusch & A. R. Woods (1993). Decidability and Undecidability of Theories with a Predicate for the Primes. Journal of Symbolic Logic 58 (2):672-687.
Paolo Casalegno (1985). On the T-Degrees of Partial Functions. Journal of Symbolic Logic 50 (3):580-588.
Added to index2009-01-28
Total downloads121 ( #22,324 of 1,726,249 )
Recent downloads (6 months)117 ( #7,454 of 1,726,249 )
How can I increase my downloads?