On the computational complexity of the theory of Abelian groups (Q1100188)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the computational complexity of the theory of Abelian groups |
scientific article |
Statements
On the computational complexity of the theory of Abelian groups (English)
0 references
1988
0 references
Using the Ehrenfeucht games method, the decidability and complexity of the following first-order theories is obtained: the theory of the divisible and indecomposable p-groups, the theory of the groups of rational numbers with denominators prime to p, the theory of cyclic groups of prime power order, the theory of direct sums of countably many infinite cyclic groups, the theory of finite Abelian groups, the theory of all Abelian groups. The author has also confirmed Gurevich's conjecture stating that the theory of all Abelian groups is elementary.
0 references
Ehrenfeucht games
0 references
decidability
0 references
complexity
0 references
first-order theories
0 references
divisible and indecomposable p-groups
0 references
groups of rational numbers with denominators prime to p
0 references
cyclic groups of prime power order
0 references
direct sums of countably many infinite cyclic groups
0 references
finite Abelian groups
0 references
Abelian groups
0 references
Gurevich's conjecture
0 references