Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T05:30:55.079Z Has data issue: false hasContentIssue false

On an algorithm to decide whether a free group is a free factor of another

Published online by Cambridge University Press:  20 December 2007

Pedro V. Silva
Affiliation:
Centro de Matemática, Faculdade de Ciências, Universidade do Porto, R. Campo Alegre 687, 4169-007 Porto, Portugal; pvsilva@fc.up.pt
Pascal Weil
Affiliation:
LaBRI, CNRS, 351 cours de la Libération, 33405 Talence Cedex, France; pascal.weil@labri.fr
Get access

Abstract

We revisit the problem of deciding whether a finitely generated subgroup H is a free factor of a given free group F. Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of H and exponential in the rank of F. We show that the latter dependency can be made exponential in the rank difference rank(F) - rank(H), which often makes a significant change.

Information

Type
Research Article
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable