On the computational complexity of the theory of Abelian groups
type: Item
instance of: scholarly article
title: On the computational complexity of the theory of Abelian groups
zbMATH Open document ID: 0639.03010
DOI: 10.1016/0168-0072(88)90020-6
author: Libo Lo
published in: Annals of Pure and Applied Logic
publication date: 1988-01-01T00:00:00Z
review text: 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.
reviewed by: M.Pałasiński
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 20K99
zbMATH DE Number: 4041862
zbMATH Keywords: Ehrenfeucht games
zbMATH Keywords: decidability
zbMATH Keywords: complexity
zbMATH Keywords: first-order theories
zbMATH Keywords: divisible and indecomposable p-groups
zbMATH Keywords: groups of rational numbers with denominators prime to p
zbMATH Keywords: cyclic groups of prime power order
zbMATH Keywords: direct sums of countably many infinite cyclic groups
zbMATH Keywords: finite Abelian groups
zbMATH Keywords: Abelian groups
zbMATH Keywords: Gurevich's conjecture
MaRDI profile type: Publication
full work available at URL: 0168-0072(88)90020-6
OpenAlex ID: W1983136104
cites work: An application of games to the completeness problem for formalized theories
cites work: The elementary theory of abelian groups
cites work: The computational complexity of logical theories
cites work: Q4082296
cites work: Q3281123
cites work: On the interval containing at least one prime number
cites work: Q4131018
cites work: Elementary properties of Abelian groups
description: scientific article; zbMATH DE number 4041862