On the complexity of intersection and conjugacy problems in free groups (Q760501): Difference between revisions

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''.