On the computational complexity of the theory of Abelian groups
Copyright policy )On the computational complexity of the theory of Abelian groups
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.
- Beijing Normal University China (People's Republic of)
- Beijing Normal University China (People's Republic of)
Complexity of computation (including implicit computational complexity), Ehrenfeucht games, Logic, decidability, groups of rational numbers with denominators prime to p, divisible and indecomposable p-groups, Decidability of theories and sets of sentences, first-order theories, cyclic groups of prime power order, finite Abelian groups, complexity, Gurevich's conjecture, Abelian groups, direct sums of countably many infinite cyclic groups
Complexity of computation (including implicit computational complexity), Ehrenfeucht games, Logic, decidability, groups of rational numbers with denominators prime to p, divisible and indecomposable p-groups, Decidability of theories and sets of sentences, first-order theories, cyclic groups of prime power order, finite Abelian groups, complexity, Gurevich's conjecture, Abelian groups, direct sums of countably many infinite cyclic groups
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!