No Access

A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS

NICHOLAS W. M. TOUIKAN

Department of Mathematics and Statistics, McGill University, Montreal, Québec, Canada

https://doi.org/10.1142/S0218196706003396Cited by:18

Abstract

Stalling's folding process is a key algorithm for solving algorithmic problems for finitely generated subgroups of free groups. Given a subgroup H = 〈J₁,…,J_m〉 of a finitely generated nonabelian free group F = F(x₁,…,x_n) the folding porcess enables one, for example, to solve the membership problem or compute the index [F : H]. We show that for a fixed free group F and an arbitrary finitely generated subgroup H (as given above) we can perform the Stallings' folding process in time O(N log*(N)), where N is the sum of the word lengths of the given generators of H.

Keywords:

AMSC: Primary 20F10, Secondary 6BR10

References

T. H. Cormen et al. , Introduction to Algorithms , 2nd edn. ( MIT Press , 2001 ) . Google Scholar
I. Kapovich and A. G. Miasnikov, J. Algebra 248(2), 608 (2002), DOI: 10.1006/jabr.2001.9033. Crossref, ISI, Google Scholar
C. C. Sims , Computation with Finitely Presented Groups ( Cambridge University Press , Cambridge , 1994 ) . Crossref, Google Scholar
J. R. Stallings, Invent. Math. 71, 551 (1983), DOI: 10.1007/BF02095993. Crossref, ISI, Google Scholar
J. R. Stallings and A. R. Wolf, Combinatorial Group Theory and Topology (Princeton University Press, Princeton, 1987) pp. 157–161. Crossref, Google Scholar
M. J. Dunwoody, Geom. Topol. (Coventry) 139 (1998), DOI: 10.2140/gtm.1998.1.139. Google Scholar
J. A. Bondy and U. S. R. Murty , Graph Theory with Applications ( American Elsevier , New York , 1976 ) . Crossref, Google Scholar