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


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


Zbl 0555.20015
Full Text: DOI


[1] Avenhaus, J.; Madlener, K., How to compute generators for the intersection of subgroups in free groups, (), 88-100 · Zbl 0466.68036
[2] 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
[3] Howson, A.G., On the intersection of finitely generated free groups, J. London math. soc., 29, 428-434, (1954) · Zbl 0056.02106
[4] Imrich, W., On finitely generated subgroups of free groups, Arch. math., 28, 21-24, (1977) · Zbl 0385.20016
[5] Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, (1977), Springer Berlin · Zbl 0368.20023
[6] Lipton, R.J.; Zalcstein, Y., Word problems solvable in logspace, J. ACM, 24, 522-526, (1977) · Zbl 0359.68049
[7] Moldavanskii, D.J., Conjugacy of subgroups of a free group, Algebra i logika, 8, 394-395, (1969) · Zbl 0229.20020
[8] 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.