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

RAIRO - Theoretical Informatics and Applications (2007)

- Volume: 42, Issue: 2, page 395-414
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topSilva, Pedro V., and Weil, Pascal. "On an algorithm to decide whether a free group is a free factor of another." RAIRO - Theoretical Informatics and Applications 42.2 (2007): 395-414. <http://eudml.org/doc/92878>.

@article{Silva2007,

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.
},

author = {Silva, Pedro V., Weil, Pascal},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Combinatorial group theory; free groups; free factors;
inverse automata; algorithms; free factor groups; inverse automata; finitely generated subgroups; lengths of generators; ranks},

language = {eng},

month = {12},

number = {2},

pages = {395-414},

publisher = {EDP Sciences},

title = {On an algorithm to decide whether a free group is a free factor of another},

url = {http://eudml.org/doc/92878},

volume = {42},

year = {2007},

}

TY - JOUR

AU - Silva, Pedro V.

AU - Weil, Pascal

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2007/12//

PB - EDP Sciences

VL - 42

IS - 2

SP - 395

EP - 414

AB -
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.

LA - eng

KW - Combinatorial group theory; free groups; free factors;
inverse automata; algorithms; free factor groups; inverse automata; finitely generated subgroups; lengths of generators; ranks

UR - http://eudml.org/doc/92878

ER -

## References

top- J. Almeida, Finite semigroups and universal algebra. World Scientific Publishing, Singapore (1994). Zbl0844.20039
- I. Anshel, M. Anshel, B. Fisher and D. Goldfeld, New key agreement protocols in braid group cryptography, in CT-RSA 2001. Lect. Notes Comput. Sci.2020 (2001) 1–15. Zbl0991.94034
- S. Cleary and J. Taback, Metric properties of the lamplighter group as an automata group. Contemp. Math.372, AMS (2005) Zbl1083.20037
- P. Dehornoy, Braid-based cryptography. Contemp. Math.360 (2004) 5–33. Zbl1083.94008
- S. Gersten, On Whitehead's algorithm. Bull. Amer. Math. Soc.10 (1984) 281–284. Zbl0537.20015
- K. Henckell, S.W. Margolis, J.-E. Pin and J. Rhodes, Ash's type II theorem, profinite topology and Malcev products. Int. J. Algebr. Comput.1 (1991) 411–436. Zbl0791.20079
- M. Kambites, P.V. Silva and B. Steinberg, The spectra of lamplighter groups and Cayley machines. Geom. Dedicata120 (2006) 193–227. Zbl1168.20012
- I. Kapovich and A.G. Miasnikov, Stallings foldings and subgroups of free groups. J. Algebra248 (2002) 608–668. Zbl1001.20015
- I. Kapovich, P. Schupp and V. Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math.223 (2006) 113–140. Zbl1149.20028
- B. Khan, The structure of automorphic conjugacy in the free group of rank two, in Proc. Special Session on Interactions between Logic, Group Theory and Computer Science. Contemp. Math.349 (2004). Zbl1078.20035
- D. Lee, A tighter bound for the number of words of minimum length in an automorphic orbit. J. Algebra305 (2006) 1093–1101. Zbl1112.20022
- R. Lyndon and P. Schupp, Combinatorial group theory. Springer (1977, reprinted 2001). Zbl0368.20023
- S. Margolis and J. Meakin, Free inverse monoids and graph immersions. Int. J. Algebr. Comput.3 (1993) 79–100. Zbl0798.20056
- S. Margolis, M. Sapir and P. Weil, Closed subgroups in pro-V topologies and the extension problem for inverse automata. Int. J. Algebr. Comput.11 (2001) 405–445. Zbl1027.20036
- A.G. Miasnikov and V. Shpilrain, Automorphic orbits in free groups. J. Algebra269 (2003) 18–27. Zbl1035.20019
- A.G. Miasnikov, E. Ventura and P. Weil, Algebraic extensions in free groups, in Geometric Group theory, Geneva and Barcelona conferences, G.N. Arzhantseva, L. Bartholdi, J. Burillo and E. Ventura, eds. Trends Math. (2007) 225-253. Zbl1160.20022
- D. Perrin, Automata, in Handbook of Theoretical Computer Science, Vol. B, J. Leeuwen ed. Elsevier, 1990.
- J.-E. Pin, Variétés de langages formels, Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986).
- J. Rotman, An introduction to the theory of groups. 4th edition, Springer (1995). Zbl0810.20001
- J.-P. Serre, Arbres, amalgames, SL2, Astérisque 46, Soc. Math. France (1977). English translation: Trees, Springer Monographs in Mathematics, Springer (2003).
- V.M. Sidelnikov, M.A. Cherepnev and V.Y. Yaschenko, Systems of open distribution of keys on the basis of non-commutative semigroups. Ross. Acd. Nauk Dokl.332-5 (1993). English translation: Russian Acad. Sci. Dokl. Math.48-2 (1994) 383–386.
- P.V. Silva and B. Steinberg, On a class of automata groups generalizing lamplighter groups. Intern. J. Algebra Comput.15 (2005) 1213–1234. Zbl1106.20028
- J. Stallings, Topology of finite graphs. Invent. Math.71 (1983) 551–565. Zbl0521.20013
- J. Stephen, Applications of automata theory to presentations of monoids and inverse monoids. Ph.D. Dissertation, University of Nebraska (1987).
- N. Touikan. A fast algorithm for Stallings? Folding process. J. Algebra Comput.16 (2006) 1031–1046. Zbl1111.20032
- E. Ventura, On fixed subgroups of maximal rank. Comm. Algebra25 (1997) 3361–3375. Zbl0893.20025