On an algorithm to decide whether a free group is a free factor of another
Preprint
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 14 references indexed in Scilit:
- Algebraic Extensions in Free Groups2007
- A tighter bound for the number of words of minimum length in an automorphic orbitJournal of Algebra, 2006
- ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPSInternational Journal of Algebra and Computation, 2005
- Metric properties of the lamplighter group as an automata group2005
- Braid-based cryptography2004
- CLOSED SUBGROUPS IN PRO-V TOPOLOGIES AND THE EXTENSION PROBLEM FOR INVERSE AUTOMATAInternational Journal of Algebra and Computation, 2001
- New Key Agreement Protocols in Braid Group Cryptography2001
- Combinatorial Group Theory2001
- On Whitehead’s algorithmBulletin of the American Mathematical Society, 1984
- Topology of finite graphsInventiones Mathematicae, 1983