On the Complexity of the Theories of Weak Direct Products
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 oper...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148871 |
| _version_ | 1811090067689570304 |
|---|---|
| author | Rackoff, Charles |
| author_facet | Rackoff, Charles |
| author_sort | Rackoff, Charles |
| collection | MIT |
| description | 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 ... |
| first_indexed | 2024-09-23T14:32:10Z |
| id | mit-1721.1/148871 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:32:10Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1488712023-03-30T03:24:26Z On the Complexity of the Theories of Weak Direct Products Rackoff, Charles 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 ... 2023-03-29T14:03:47Z 2023-03-29T14:03:47Z 1974-01 https://hdl.handle.net/1721.1/148871 09610055 MIT-LCS-TM-042 MAC-TM-042 application/pdf |
| spellingShingle | Rackoff, Charles On the Complexity of the Theories of Weak Direct Products |
| title | On the Complexity of the Theories of Weak Direct Products |
| title_full | On the Complexity of the Theories of Weak Direct Products |
| title_fullStr | On the Complexity of the Theories of Weak Direct Products |
| title_full_unstemmed | On the Complexity of the Theories of Weak Direct Products |
| title_short | On the Complexity of the Theories of Weak Direct Products |
| title_sort | on the complexity of the theories of weak direct products |
| url | https://hdl.handle.net/1721.1/148871 |
| work_keys_str_mv | AT rackoffcharles onthecomplexityofthetheoriesofweakdirectproducts |