Magnus embedding and algorithmic properties of groups F/N^(d)

DOI10.1090/TRAN/6880zbMATH Open1434.20021arXiv1501.01001OpenAlexW2964051707MaRDI QIDQ5267968FDOQ5267968

Funda Gul, Alexander Ushakov, Mahmood Sohrabi

Publication date: 14 June 2017

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

Abstract: In this paper we further study properties of Magnus embedding, give a precise reducibility diagram for Dehn problems in groups of the form $F/N^{(d)}$, and provide a detailed answer to Problem 12.98 in Kourovka notebook. We also show that most of the reductions are polynomial time reductions and can be used in practical computation.

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

Recommendations

• Group Embeddings with Algorithmic Properties
• Metric behaviour of the Magnus embedding.
• Algorithmic and asymptotic properties of groups.
• Isoperimetric functions of groups and computational complexity of the word problem
• The word and geodesic problems in free solvable groups.

zbMATH Keywords

conjugacy problemword problemfree solvable groupspower problemMagnus embedding

Mathematics Subject Classification ID

Generalizations of solvable and nilpotent groups (20F19) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Topology of finite graphs
• The word and geodesic problems in free solvable groups
• Knapsack problems in groups
• Knapsack problems in products of groups
• Title not available (Why is that?)
• Stallings foldings and subgroups of free groups
• On a theorem of Marshall Hall
• On quasilinear-time complexity theory
• Title not available (Why is that?)
• Polynomial time conjugacy in wreath products and free solvable groups.
• Algorithmic theory of free solvable groups: randomized computations.
• The Conjugacy Problem in Wreath Products and Free Metabelian Groups
• Limit groups as limits of free groups.
• Commutator Subgroups of Free Groups
• Title not available (Why is that?)
• On the Conjugacy Problem for F/R �
• On the word problem and the conjugacy problem for groups of the form \(F/V(R)\)
• Spherical quadratic equations in free metabelian groups.
• THE MAGNUS EMBEDDING IS A QUASI-ISOMETRY

Cited In (4)

• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• Orientable quadratic equations in free metabelian groups
• Generalized Magnus embeddings and some residual properties of groups and group rings
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)

This page was built for publication: Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)

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