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

DOI10.1051/ITA:2007040zbMATH Open1146.20021arXivmath/0609552OpenAlexW2056115496MaRDI QIDQ3515469FDOQ3515469

Authors: Pedro V. Silva, Pascal Weil 

Publication date: 29 July 2008

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0609552

Recommendations

• Computing fixed closures in free groups.
• Complementing a subgroup of a hyperbolic group by a free factor.
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• The monomorphism problem in free groups.
• Subgroups of free groups and primitive elements

zbMATH Keywords

algorithmsranksfree groupsfinitely generated subgroupsfree factor groupsinverse automatalengths of generators

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Free nonabelian groups (20E05) Generators, relations, and presentations of groups (20F05) Algebraic theory of languages and automata (68Q70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Topology of finite graphs
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• Stallings foldings and subgroups of free groups
• CLOSED SUBGROUPS IN PRO-V TOPOLOGIES AND THE EXTENSION PROBLEM FOR INVERSE AUTOMATA
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automorphic orbits in free groups.
• Title not available (Why is that?)
• A tighter bound for the number of words of minimum length in an automorphic orbit.
• Title not available (Why is that?)
• The spectra of lamplighter groups and Cayley machines.
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• On Whitehead’s algorithm
• Title not available (Why is that?)
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• On fixed subgroups of maximal rank
• Title not available (Why is that?)

Cited In (12)

• A list of applications of Stallings automata
• On the lattice of subgroups of a free group: complements and rank
• Onto extensions of free groups
• An algorithm to recognize echelon subgroups of a free group
• Generic properties of subgroups of free groups and finite presentations
• Relative order and spectrum in free and related groups
• On free-group algorithms that sandwich a subgroup between free-product factors.
• Title not available (Why is that?)
• Stallings automata for free-times-abelian groups: intersections and index
• Primitive words, free factors and measure preservation.
• On finite-index extensions of subgroups of free groups.
• Automorphic orbits in free groups: words versus subgroups.

This page was built for publication: On an algorithm to decide whether a free group is a free factor of another

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3515469)