On the complexity of intersection and conjugacy problems in free groups

DOI10.1016/0304-3975(84)90046-XMaRDI QIDQ760501zbMATH OpenOpenAlexFDO

Authors Jürgen Avenhaus, Klaus Madlener

Publication date 1984

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(84)90046-x

zbMATH Keywords

algorithmsconjugacy problemdecision problemsfree groupsHowson propertylog-space reducibilitypolynomially time completeset of generators

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• The Nielsen reduction and P-complete problems in free groups
• scientific article; zbMATH DE number 3874607
• scientific article; zbMATH DE number 8769
• Efficiency of certain algorithms of combinatorial group theory
• On the conjugacy problem in the group F/N₁ N₂.

Cites work

• Conjugacy of subgroups of a free group
• scientific article; zbMATH DE number 3731337 (Why is no real title available?)
• scientific article; zbMATH DE number 3563392 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• On finitely generated subgroups of free groups
• On the Intersection of Finitely Generated Free Groups
• The Nielsen reduction and P-complete problems in free groups
• Word Problems Solvable in Logspace

Cited in

(19)

• Thue systems as rewriting systems
• Parallel algorithms for solvable permutation groups
• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
• Algorithmic problems for free-Abelian times free groups.
• On the multiple conjugacy problem in group \(F/N_1 \cap N_2\)
• On the complexity of the endomorphism problem for free groups.
• Polynomial time conjugacy in wreath products and free solvable groups.
• scientific article; zbMATH DE number 6004943 (Why is no real title available?)
• scientific article; zbMATH DE number 3874607 (Why is no real title available?)
• On the conjugacy problem in the group F/N₁ N₂.
• Efficiency of certain algorithms of combinatorial group theory
• scientific article; zbMATH DE number 8769 (Why is no real title available?)
• On the parallel complexity of linear groups
• Algorithmic theory of free solvable groups: randomized computations.
• The computational complexity of torsion-freeness of finitely presented groups
• PSPACE-completeness of certain algorithmic problems on the subgroups of free groups
• scientific article; zbMATH DE number 2144681 (Why is no real title available?)
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
• GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS

This page was built for publication: On the complexity of intersection and conjugacy problems in free groups

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