On the Complexity of the Theories of Weak Direct Products
Author(s)
Rackoff, Charles![Thumbnail](/bitstream/handle/1721.1/148871/MIT-LCS-TM-042.pdf.jpg?sequence=3&isAllowed=y)
DownloadMIT-LCS-TM-042.pdf (859.6Kb)
Metadata
Show full item recordAbstract
Let N be the set of nonnegative integers and let < N ,+> be the weak direct product of < N,+> with itself. Mostowski[ 9 ] shows that the theory of < N ,*> is decidable, but his decision procedure isn't elementary recursive. We present here a more efficient procedure which operates within space 2 2 . As corollaries we obtain the same upper bound for the theory of finite abelian groups, the theory of finitely generated abelian groups, and the theory of the structure < N ,' > of positive ...
Date issued
1974-01Series/Report no.
MIT-LCS-TM-042MAC-TM-042