## On the complexity of intersection and conjugacy problems in free groups.(English)Zbl 0555.20016

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”.
Reviewer: S.J.Pride

### MSC:

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

Zbl 0555.20015
Full Text:

### References:

  Avenhaus, J.; Madlener, K., How to compute generators for the intersection of subgroups in free groups, (), 88-100 · Zbl 0466.68036  Avenhaus, J.; Madlener, K., The Nielsen reduction and P-complete problems in free groups, Theoret. comput. sci., 32, 1, 2, 61-76, (1984) · Zbl 0555.20015  Howson, A.G., On the intersection of finitely generated free groups, J. London math. soc., 29, 428-434, (1954) · Zbl 0056.02106  Imrich, W., On finitely generated subgroups of free groups, Arch. math., 28, 21-24, (1977) · Zbl 0385.20016  Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, (1977), Springer Berlin · Zbl 0368.20023  Lipton, R.J.; Zalcstein, Y., Word problems solvable in logspace, J. ACM, 24, 522-526, (1977) · Zbl 0359.68049  Moldavanskii, D.J., Conjugacy of subgroups of a free group, Algebra i logika, 8, 394-395, (1969) · Zbl 0229.20020  Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory, (1976), Dover Publications New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.