An algebraic characterization of groups with soluble word problem

DOI10.1017/S1446788700019108zbMath0303.20028MaRDI QIDQ4059096

William W. Boone, Graham Higman

Publication date: 1974

Published in: Journal of the Australian Mathematical Society (Search for Journal in Brave)

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items

Group Embeddings with Algorithmic Properties ⋮ On the isolated points in the space of groups. ⋮ Unsolvable algorithmic problems for semigroups, groups and rings ⋮ Groups whose word problems are accepted by abelian \(G\)-automata ⋮ Groups finitely presented in Burnside varieties ⋮ Algebraic equivalents of the solvability of group-theoretic algorithmic problems ⋮ Embeddings into left‐orderable simple groups ⋮ Finite semigroups embed in finitely presented congruence-free monoids. ⋮ Infinite groups ⋮ Decidable fragments of universal theories and existentially closed models ⋮ Embeddings into Simple Free Products ⋮ Groups of Automorphisms of Totally Ordered Sets: Techniques, Model Theory and Applications to Decision Problems ⋮ Automorphism groups of totally ordered sets: A retrospective survey ⋮ The loop problem for Rees matrix semigroups. ⋮ Gruppen mit vorgeschriebenem Wortproblem ⋮ Logical aspects of Cayley-graphs: the group case ⋮ Infinitely generated subgroups of finitely presented groups. I ⋮ ON GROUPS AND COUNTER AUTOMATA ⋮ Filters in lattices of quasivarieties of algebraic systems ⋮ Unnamed Item ⋮ Satisfaction of existential theories in finitely presented groups and some embedding theorems. ⋮ A characterization of the subgroups of finitely presented groups ⋮ Finitely generated lattice-ordered groups with soluble word problem ⋮ An algebra has a solvable word problem if and only if it is embeddable in a finitely generated simple algebra ⋮ Word problems ⋮ The Boone-Higman theorem and the conjugacy problem ⋮ Constructing finitely presented simple groups that contain Grigorchuk groups ⋮ Simplicity and superrigidity of twin building lattices. ⋮ The word problem of the Brin-Thompson group is \textsf{coNP}-complete ⋮ A countable family of finitely presented infinite congruence-free monoids ⋮ Finitely determined members of varieties of groups and rings ⋮ Model-theoretic and algorithmic questions in group theory

Cites Work

• Unnamed Item
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• Subgroups of finitely presented groups
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• An Embedding Theorem for Finitely Generated Groups
• On a Problem of J.H.C. Whitehead and a Problem of Alonzo Church.
• Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
• The word problem for semigroups with two generators
• Embedding Theorems for Groups
• The word problem