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

DOI10.1051/ITA:2007040MaRDI QIDQ3515469zbMATH OpenOpenAlexFDO

Authors Pedro V. Silva, Pascal Weil

Publication date 29 July 2008

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

Full work available at URL https://arxiv.org/abs/math/0609552, https://eudml.org/doc/92878

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)

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.

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

Cites work

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

Cited in

(12)

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

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)