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)

Review text

This paper is a continuation of the paper reviewed above. Like its predecessor, this paper is aimed very much at the computer scientist. From the authors' abstract: Having a Nielsen reduced set of generators for subgroups H and K [of a free group F] one can solve a lot of intersection and conjugacy problems in polynomial time in a uniform way. We study the solvability of (i)\(\exists h\in H\), \(k\in K:\) \(hx=yk\) in F, and (ii) \(\exists w\in F\) \(w^{-1}Hw=K\) and characterize the set of solutions. This leads for (i) to an algorithm for computing a set of generators for \(H\cap K\) (and a new proof that free groups have the Howson property). For (ii) this gives a fast solution of Moldavanskij's conjugacy problem; an algorithm for computing the normal hull of H then gives a representation of all solutions. All the algorithms run in polynomial time and the decision problems are proved to be P-complete under log-space reducibility.

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)