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)|
References found in this work BETA
No references found.
Citations of this work BETA
A Uniform Method for Proving Lower Bounds on the Computational Complexity of Logical Theories.J. Compton Kevin & C. Ward Henson - 1990 - Annals of Pure and Applied Logic 48 (1):1-79.
On the Computational Complexity of the Theory of Abelian Groups.Libo Lo - 1988 - Annals of Pure and Applied Logic 37 (3):205-248.
Similar books and articles
Undecidable Extensions of Skolem Arithmetic.Alexis Bés & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.
Splitting Properties of N-C.E. Enumeration Degrees.I. Sh Kalimullin - 2002 - Journal of Symbolic Logic 67 (2):537-546.
The Theory of All Substructures of a Structure: Characterisation and Decision Problems.Kenneth L. Manders - 1979 - Journal of Symbolic Logic 44 (4):583-598.
A Downward Löwenheim-Skolem Theorem for Infinitary Theories Which Have the Unsuperstability Property.Rami Grossberg - 1988 - Journal of Symbolic Logic 53 (1):231-242.
Undecidable Extensions of Büchi Arithmetic and Cobham-Semënov Theorem.Alexis Bès - 1997 - Journal of Symbolic Logic 62 (4):1280-1296.
Reducts of Some Structures Over the Reals.Ya'acov Peterzil - 1993 - Journal of Symbolic Logic 58 (3):955-966.
Equivalence Elementaire Et Decidabilite Pour Des Structures du Type Groupe Agissant Sur Un Groupe Abelien.Patrick Simonetta - 1998 - Journal of Symbolic Logic 63 (4):1255-1285.
Decidability and Undecidability of Theories with a Predicate for the Primes.P. T. Bateman, C. G. Jockusch & A. R. Woods - 1993 - Journal of Symbolic Logic 58 (2):672-687.
Added to index2009-01-28
Total downloads202 ( #20,392 of 2,171,743 )
Recent downloads (6 months)2 ( #173,816 of 2,171,743 )
How can I increase my downloads?