On an algorithm to decide whether a free group is a free factor of another
Silva, Pedro V. ; Weil, Pascal
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 395-414 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2007040
Classification:  20E05,  05C25 
@article{ITA_2008__42_2_395_0,
     author = {Silva, Pedro V. and Weil, Pascal},
     title = {On an algorithm to decide whether a free group is a free factor of another},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {395-414},
     doi = {10.1051/ita:2007040},
     mrnumber = {2401269},
     zbl = {1146.20021},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_2_395_0}
}

Silva, Pedro V.; Weil, Pascal. On an algorithm to decide whether a free group is a free factor of another. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 395-414. doi : 10.1051/ita:2007040. http://gdmltest.u-ga.fr/item/ITA_2008__42_2_395_0/

[1] J. Almeida, Finite semigroups and universal algebra. World Scientific Publishing, Singapore (1994). | MR 1331143 | Zbl 0844.20039

[2] 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. | Zbl 0991.94034

[3] S. Cleary and J. Taback, Metric properties of the lamplighter group as an automata group. Contemp. Math. 372, AMS (2005) | MR 2140090 | Zbl 1083.20037

[4] P. Dehornoy, Braid-based cryptography. Contemp. Math. 360 (2004) 5-33. | MR 2105432 | Zbl 1083.94008

[5] S. Gersten, On Whitehead's algorithm. Bull. Amer. Math. Soc. 10 (1984) 281-284. | MR 733696 | Zbl 0537.20015

[6] 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. | MR 1154442 | Zbl 0791.20079

[7] M. Kambites, P.V. Silva and B. Steinberg, The spectra of lamplighter groups and Cayley machines. Geom. Dedicata 120 (2006) 193-227. | MR 2252901 | Zbl pre05053972

[8] I. Kapovich and A.G. Miasnikov, Stallings foldings and subgroups of free groups. J. Algebra 248 (2002) 608-668. | MR 1882114 | Zbl 1001.20015

[9] 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. | MR 2221020 | Zbl 1149.20028

[10] 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). | MR 2077762 | Zbl 1078.20035

[11] D. Lee, A tighter bound for the number of words of minimum length in an automorphic orbit. J. Algebra 305 (2006) 1093-1101. | MR 2266870 | Zbl 1112.20022

[12] R. Lyndon and P. Schupp, Combinatorial group theory. Springer (1977, reprinted 2001). | MR 577064 | Zbl 0997.20037 | Zbl 0368.20023

[13] S. Margolis and J. Meakin, Free inverse monoids and graph immersions. Int. J. Algebr. Comput. 3 (1993) 79-100. | MR 1214007 | Zbl 0798.20056

[14] 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. | MR 1850210 | Zbl 1027.20036

[15] A.G. Miasnikov and V. Shpilrain, Automorphic orbits in free groups. J. Algebra 269 (2003) 18-27. | MR 2015300 | Zbl 1035.20019

[16] 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. | MR 2395796 | Zbl 1160.20022

[17] D. Perrin, Automata, in Handbook of Theoretical Computer Science, Vol. B, J. Leeuwen ed. Elsevier, 1990. | MR 1127186 | Zbl 0900.68312

[18] J.-E. Pin, Variétés de langages formels, Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986). | MR 752695 | Zbl 0636.68093

[19] J. Rotman, An introduction to the theory of groups. 4th edition, Springer (1995). | MR 1307623 | Zbl 0810.20001

[20] J.-P. Serre, Arbres, amalgames, SL 2 , Astérisque 46, Soc. Math. France (1977). English translation: Trees, Springer Monographs in Mathematics, Springer (2003). | MR 476875 | Zbl 0369.20013

[21] 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. | Zbl 0823.94015

[22] P.V. Silva and B. Steinberg, On a class of automata groups generalizing lamplighter groups. Intern. J. Algebra Comput. 15 (2005) 1213-1234. | MR 2197829 | Zbl 1106.20028

[23] J. Stallings, Topology of finite graphs. Invent. Math. 71 (1983) 551-565. | MR 695906 | Zbl 0521.20013

[24] J. Stephen, Applications of automata theory to presentations of monoids and inverse monoids. Ph.D. Dissertation, University of Nebraska (1987).

[25] N. Touikan. A fast algorithm for Stallings? Folding process. J. Algebra Comput. 16 (2006) 1031-1046. | MR 2286421 | Zbl 1111.20032

[26] E. Ventura, On fixed subgroups of maximal rank. Comm. Algebra 25 (1997) 3361-3375. | MR 1465119 | Zbl 0893.20025