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 problemfree groupsdecision problemsHowson propertyset of generatorslog-space reducibilitypolynomially time complete

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

• 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?)
• Conjugacy of subgroups of a free group
• 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

(16)

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

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)