×

zbMATH — the first resource for mathematics

Decision problems for groups – survey and reflections. (English) Zbl 0752.20014
Algorithms and classification in combinatorial group theory, Lect. Workshop, Berkeley/CA (USA) 1989, Publ., Math. Sci. Res. Inst. 23, 1-59 (1992).
[For the entire collection see Zbl 0742.00063.]
From the author’s introduction: “…Naturally the choice of material reported on reflects the author’s interests and many worthy contributions to the field will unfortunately go without mention. A number of relatively straight forward proofs have been included; usually they are not too difficult, or illustrate the concepts involved or even, occasionally, have a novel aspect. Many concepts and results from mathematical logic, particularly recursive function theory, are explained in an informal manner and occasionally at some length. Hopefully this will make these concepts more accessible for a wide audience.”
The author divides decision problems into local and global ones with respect to whether they concern the properties of elements or that of groups as a whole. The following topics are covered: basic local and global unsolvability results (with the proof of the Adyan-Rabin theorem and discussion of arithmetic hierarchy); behaviour of decision problems with respect to group constructions; decision problems in various classes of groups – solvable, linear, hopfian, residually nilpotent (free, finite), one-relator, simple, small cancellation groups; geometry and complexity (including diagrams, Dehn’s algorithm and hyperbolic groups, automatic groups, normal form and rewriting systems); computability of homological invariants.
Reviewer: G.A.Noskov (Omsk)

MSC:
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
03D20 Recursive functions and relations, subrecursive hierarchies
03D40 Word problems, etc. in computability and recursion theory
PDF BibTeX XML Cite