We revisit the problem of deciding whether a finitely generated subgroup is a free factor of a given free group . Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of and exponential in the rank of . We show that the latter dependency can be made exponential in the rank difference rank - rank, which often makes a significant change.
Mots-clés : combinatorial group theory, free groups, free factors, inverse automata, algorithms
@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},
pages = {395--414},
publisher = {EDP-Sciences},
volume = {42},
number = {2},
year = {2008},
doi = {10.1051/ita:2007040},
mrnumber = {2401269},
zbl = {1146.20021},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007040/}
}
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 - Informatique Théorique et Applications PY - 2008 SP - 395 EP - 414 VL - 42 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2007040/ DO - 10.1051/ita:2007040 LA - en ID - ITA_2008__42_2_395_0 ER -
%0 Journal Article %A Silva, Pedro V. %A Weil, Pascal %T On an algorithm to decide whether a free group is a free factor of another %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 395-414 %V 42 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2007040/ %R 10.1051/ita:2007040 %G en %F 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) no. 2, pp. 395-414. doi : 10.1051/ita:2007040. http://www.numdam.org/articles/10.1051/ita:2007040/
[1] , Finite semigroups and universal algebra. World Scientific Publishing, Singapore (1994). | MR | Zbl
[2] , , and , New key agreement protocols in braid group cryptography, in CT-RSA 2001. Lect. Notes Comput. Sci. 2020 (2001) 1-15. | Zbl
[3] and , Metric properties of the lamplighter group as an automata group. Contemp. Math. 372, AMS (2005) | MR | Zbl
[4] , Braid-based cryptography. Contemp. Math. 360 (2004) 5-33. | MR | Zbl
[5] , On Whitehead's algorithm. Bull. Amer. Math. Soc. 10 (1984) 281-284. | MR | Zbl
[6] , , and , Ash's type II theorem, profinite topology and Malcev products. Int. J. Algebr. Comput. 1 (1991) 411-436. | MR | Zbl
[7] , and , The spectra of lamplighter groups and Cayley machines. Geom. Dedicata 120 (2006) 193-227. | MR
[8] and , Stallings foldings and subgroups of free groups. J. Algebra 248 (2002) 608-668. | MR | Zbl
[9] , and , Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math. 223 (2006) 113-140. | MR | Zbl
[10] , 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 | Zbl
[11] , A tighter bound for the number of words of minimum length in an automorphic orbit. J. Algebra 305 (2006) 1093-1101. | MR | Zbl
[12] and , Combinatorial group theory. Springer (1977, reprinted 2001). | MR | Zbl
[13] and , Free inverse monoids and graph immersions. Int. J. Algebr. Comput. 3 (1993) 79-100. | MR | Zbl
[14] , and , Closed subgroups in pro-V topologies and the extension problem for inverse automata. Int. J. Algebr. Comput. 11 (2001) 405-445. | MR | Zbl
[15] and , Automorphic orbits in free groups. J. Algebra 269 (2003) 18-27. | MR | Zbl
[16] , and , 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 | Zbl
[17] , Automata, in Handbook of Theoretical Computer Science, Vol. B, J. Leeuwen ed. Elsevier, 1990. | MR | Zbl
[18] , Variétés de langages formels, Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986). | MR | Zbl
[19] , An introduction to the theory of groups. 4th edition, Springer (1995). | MR | Zbl
[20] , Arbres, amalgames, , Astérisque 46, Soc. Math. France (1977). English translation: Trees, Springer Monographs in Mathematics, Springer (2003). | Numdam | MR | Zbl
[21] , and , 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
[22] and , On a class of automata groups generalizing lamplighter groups. Intern. J. Algebra Comput. 15 (2005) 1213-1234. | MR | Zbl
[23] , Topology of finite graphs. Invent. Math. 71 (1983) 551-565. | EuDML | MR | Zbl
[24] , Applications of automata theory to presentations of monoids and inverse monoids. Ph.D. Dissertation, University of Nebraska (1987).
[25] . A fast algorithm for Stallings? Folding process. J. Algebra Comput. 16 (2006) 1031-1046. | MR | Zbl
[26] , On fixed subgroups of maximal rank. Comm. Algebra 25 (1997) 3361-3375. | MR | Zbl
Cité par Sources :
