The Nielsen reduction and P-complete problems in free groups. (English) Zbl 0555.20015

This paper is written very much for the computer scientist. The authors consider various problems concerning free groups, such as: the generalized word problem; the determination of shortest coset representatives modulo a given subgroup; to decide whether two subgroups are equal or isomorphic; to decide whether a given set of elements freely generates a subgroup, to decide whether a subgroup has finite index. They show that these problems are polynomially time complete under log-space reducibility. The main tool used is a careful analysis of the Nielsen reduction process.
Reviewer: S.J.Pride


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


[1] Avenhaus, J.; Madlener, K., String matching and algorithmic problems in free groups, Rev. coll. math., 14, 1-16, (1980) · Zbl 0514.20026
[2] Avenhaus, J.; Madlener, K., Algorithmische probleme bei einrelatorgruppen und ihre komplexität, Arch. math. logik, 19, 3-12, (1978) · Zbl 0396.03040
[3] Avenhaus, J.; Madlener, K.; Avenhaus, J.; Madlener, K., Subrekursive komplexität bei gruppen, II, Acta informatica, Acta informatica, 9, 183-193, (1978) · Zbl 0371.02020
[4] Avenhaus, J.; Madlener, K., P-complete problems in free groups, (), 42-51, Lecture Notes in Comput. Sci. · Zbl 0867.68096
[5] Avenhaus, J.; Madlener, K., The Nielsen reduction as a key problem to polynomial algorithms in free groups, (), 49-56, Lecture Notes in Comput. Sci. · Zbl 0548.68038
[6] Jones, N.D.; Laaser, W.T., Complete problems for deterministic polynomial time, Theoret. comput. sci., 3, 105-117, (1977) · Zbl 0352.68068
[7] Lipton, R.J.; Zalcstein, Y., Word problems solvable in log-space, J. ACM, 24, 522-526, (1977) · Zbl 0359.68049
[8] Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, (1977), Springer Berlin · Zbl 0368.20023
[9] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory, (1976), Dover Publ 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.