Group Embeddings with Algorithmic Properties

DOI10.1080/00927872.2014.955579zbMATH Open1337.20036arXiv1708.04397OpenAlexW1777911311MaRDI QIDQ3448552FDOQ3448552

Arman Darbinyan

Publication date: 26 October 2015

Published in: Communications in Algebra (Search for Journal in Brave)

Abstract: We show that every countable group H with solvable word problem (=computable group) can be subnormally embedded into a 2-generated group G which also has solvable word problem. Moreover, the membership problem for H < G is also solvable. We also give estimates of time and space complexity of the word problem in G and of the membership problem for H < G.

Full work available at URL: https://arxiv.org/abs/1708.04397

zbMATH Keywords

wreath productsspace complexitytime complexityword problem2-generator groupsmembership problemembeddings of groupssubnormal embeddings

Mathematics Subject Classification ID

Extensions, wreath products, and other compositions of groups (20E22) Generators, relations, and presentations of groups (20F05) Subgroup theorems; subgroup growth (20E07) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• Varieties of groups
• Embedding Theorems for Groups
• Embedding theorems for residually finite groups
• Embedding Theorems for Groups
• On the embedding of a group in a join of given groups
• Embedding Methods for Periodic Groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Isoperimetric and isodiametric functions of groups
• Space functions of groups.
• On the Finiteness of Certain Soluble Groups
• An Embedding Theorem for Finitely Generated Groups
• An algebraic characterization of groups with soluble word problem
• On Embedding Groups and the Conjugacy Problem
• Subnormal Embedding Theorems for Groups
• An Embedding Construction for Ordered Groups

Cited In (9)

• Embeddings into left‐orderable simple groups
• On embeddings of countable generalized soluble groups into two-generated groups
• On decidability of amenability in computable groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Title not available (Why is that?)
• Implementation of Stanley's algorithm for projective group imbeddings
• Groups with decidable word problem that do not embed in groups with decidable conjugacy problem
• An Embedding Construction for Ordered Groups
• COMPUTABILITY, ORDERS, AND SOLVABLE GROUPS

   Recommendations

• Embeddings into efficient groups 👍 👎
• Embeddings into \(k\)-efficient groups. 👍 👎
• Algorithmic and asymptotic properties of groups. 👍 👎
• Title not available (Why is that?) 👍 👎
• Towards effective algorithms for linear groups. 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Embedding arbitrary algebras in groups 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Group Embeddings with Algorithmic Properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448552)