On an algorithm to decide whether a free group is a free factor of another
- 20 December 2007
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 42 (2) , 395-414
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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- A tighter bound for the number of words of minimum length in an automorphic orbitJournal of Algebra, 2006
- The spectra of lamplighter groups and Cayley machinesGeometriae Dedicata, 2006
- Generic properties of Whitehead’s algorithm and isomorphism rigidity of random one-relator groupsPacific Journal of Mathematics, 2006
- Automorphic orbits in free groupsJournal of Algebra, 2003
- Stallings Foldings and Subgroups of Free GroupsJournal of Algebra, 2002
- CLOSED SUBGROUPS IN PRO-V TOPOLOGIES AND THE EXTENSION PROBLEM FOR INVERSE AUTOMATAInternational Journal of Algebra and Computation, 2001
- Faster Generation of NICE-Schnorr-Type Signatures2001
- FREE INVERSE MONOIDS AND GRAPH IMMERSIONSInternational Journal of Algebra and Computation, 1993
- ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART IInternational Journal of Algebra and Computation, 1991
- On Whitehead’s algorithmBulletin of the American Mathematical Society, 1984