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

Pedro V. Silva; Pascal Weil

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

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

Abstract

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

How to cite

top

Silva, 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 - Informatique Théorique et Applications 42.2 (2008): 395-414. <http://eudml.org/doc/245285>.

@article{Silva2008,
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 - Informatique Théorique et Applications},
keywords = {combinatorial group theory; free groups; free factors; inverse automata; algorithms; free factor groups; finitely generated subgroups; lengths of generators; ranks},
language = {eng},
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/245285},
volume = {42},
year = {2008},
}

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
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; finitely generated subgroups; lengths of generators; ranks
UR - http://eudml.org/doc/245285
ER -

References

top
  1. [1] J. Almeida, Finite semigroups and universal algebra. World Scientific Publishing, Singapore (1994). Zbl0844.20039MR1331143
  2. [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. Zbl0991.94034
  3. [3] S. Cleary and J. Taback, Metric properties of the lamplighter group as an automata group. Contemp. Math. 372, AMS (2005) Zbl1083.20037MR2140090
  4. [4] P. Dehornoy, Braid-based cryptography. Contemp. Math. 360 (2004) 5–33. Zbl1083.94008MR2105432
  5. [5] S. Gersten, On Whitehead’s algorithm. Bull. Amer. Math. Soc. 10 (1984) 281–284. Zbl0537.20015MR733696
  6. [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. Zbl0791.20079MR1154442
  7. [7] M. Kambites, P.V. Silva and B. Steinberg, The spectra of lamplighter groups and Cayley machines. Geom. Dedicata 120 (2006) 193–227. Zbl1168.20012MR2252901
  8. [8] I. Kapovich and A.G. Miasnikov, Stallings foldings and subgroups of free groups. J. Algebra 248 (2002) 608–668. Zbl1001.20015MR1882114
  9. [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. Zbl1149.20028MR2221020
  10. [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). Zbl1078.20035MR2077762
  11. [11] D. Lee, A tighter bound for the number of words of minimum length in an automorphic orbit. J. Algebra 305 (2006) 1093–1101. Zbl1112.20022MR2266870
  12. [12] R. Lyndon and P. Schupp, Combinatorial group theory. Springer (1977, reprinted 2001). Zbl0368.20023MR577064
  13. [13] S. Margolis and J. Meakin, Free inverse monoids and graph immersions. Int. J. Algebr. Comput. 3 (1993) 79–100. Zbl0798.20056MR1214007
  14. [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. Zbl1027.20036MR1850210
  15. [15] A.G. Miasnikov and V. Shpilrain, Automorphic orbits in free groups. J. Algebra 269 (2003) 18–27. Zbl1035.20019MR2015300
  16. [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. Zbl1160.20022MR2395796
  17. [17] D. Perrin, Automata, in Handbook of Theoretical Computer Science, Vol. B, J. Leeuwen ed. Elsevier, 1990. Zbl0900.68312MR1127186
  18. [18] J.-E. Pin, Variétés de langages formels, Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986). Zbl0636.68093MR752695
  19. [19] J. Rotman, An introduction to the theory of groups. 4th edition, Springer (1995). Zbl0810.20001MR1307623
  20. [20] J.-P. Serre, Arbres, amalgames, S L 2 , Astérisque 46, Soc. Math. France (1977). English translation: Trees, Springer Monographs in Mathematics, Springer (2003). Zbl0369.20013MR476875
  21. [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. Zbl0823.94015
  22. [22] P.V. Silva and B. Steinberg, On a class of automata groups generalizing lamplighter groups. Intern. J. Algebra Comput. 15 (2005) 1213–1234. Zbl1106.20028MR2197829
  23. [23] J. Stallings, Topology of finite graphs. Invent. Math. 71 (1983) 551–565. Zbl0521.20013MR695906
  24. [24] J. Stephen, Applications of automata theory to presentations of monoids and inverse monoids. Ph.D. Dissertation, University of Nebraska (1987). 
  25. [25] N. Touikan. A fast algorithm for Stallings? Folding process. J. Algebra Comput. 16 (2006) 1031–1046. Zbl1111.20032MR2286421
  26. [26] E. Ventura, On fixed subgroups of maximal rank. Comm. Algebra 25 (1997) 3361–3375. Zbl0893.20025MR1465119

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.