On the complexity of the theories of weak direct powers
Journal of Symbolic Logic 41 (3):561-573 (1976)
| Abstract | Mostowski [11] 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 [7] 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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,664 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesAlexis 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.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
