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

• Type: Article in International Scientific Journal
• Date: 2008

Authors

Pedro V. Silva (Author) FCUP; Pascal Weil (Author) Other

Journal

Title: RAIRO - Theoretical Informatics and Applications

Vol. 42

Pages: 395-414

ISSN: 0988-3754

Publisher: EDP Sciences

Indexing

ISI Web of Knowledge - 10 Citations

ISI Web of Science

Scopus - 12 Citations

Scientific classification

FOS: Natural sciences > Mathematics

Other information

Authenticus ID: P-004-0QG

DOI: 10.1051/ita:2007040

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 20