×

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

MSC:

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

References:

[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., Subrekursive Komplexität bei Gruppen, II, Acta Informatica, 9, 183-193 (1978) · Zbl 0371.02020
[4] Avenhaus, J.; Madlener, K., P-complete problems in free groups, (GI Conf., 104 (1981), Springer: Springer Berlin), 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, (EUROCAM, 144 (1982), Springer: Springer Berlin), 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: Springer Berlin · Zbl 0368.20023
[9] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory (1976), Dover Publ: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.