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

Simple item page
dc.creatorSilva, Pedro
dc.creatorWeil, Pascal
dc.date2006-09-20
dc.date2006-11-16
dc.date.accessioned2026-07-07T09:54:03Z
dc.date.available2026-07-07T09:54:03Z
dc.descriptionWe 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.
dc.description20 pages
dc.identifierhttps://arxiv.org/abs/math/0609552
dc.identifierhttp://arxiv.org/abs/math/0609552
dc.identifierTheoretical Informatics and Applications 42 (2008) 395-414
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/166173
dc.subjectGroup Theory
dc.subject20E05; 05C25
dc.titleOn an algorithm to decide whether a free group is a free factor of another
dc.typetext

Files

Collections

arXiv