Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1051/ita:2007040 | RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS |
Keywords | Field | DocType |
combinatorial group theory,free groups,free factors,inverse automata,algorithms | Combinatorics,Exponential function,Polynomial,Group theory,Algorithm,Combinatorial group theory,Rank of an abelian group,Time complexity,Mathematics,Free probability,Free group | Journal |
Volume | Issue | ISSN |
42 | 2 | 0988-3754 |
Citations | PageRank | References |
3 | 0.69 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pedro V. Silva | 1 | 141 | 29.42 |
| Pascal Weil | 2 | 71 | 7.01 |