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
    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

    Identifiers