RAIRO-Theor. Inf. Appl. 42, 395-414 (2008)
DOI: 10.1051/ita:2007040

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

Pedro V. Silva¹ and Pascal Weil<sup>2

1</sup>  Centro de Matemática, Faculdade de Ciências, Universidade do Porto, R. Campo Alegre 687, 4169-007 Porto, Portugal; pvsilva@fc.up.pt
²  LaBRI, CNRS, 351 cours de la Libération, 33405 Talence Cedex, France; pascal.weil@labri.fr

(Received January 25, 2005. Accepted October 8, 2007. Published online 20 December 2007.)

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.

Mathematics Subject Classification. 20E05, 05C25

Key words: Combinatorial group theory -- free groups -- free factors -- inverse automata -- algorithms


© EDP Sciences 2007