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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2008

Autores

Pedro V. Silva (Autor) FCUP; Pascal Weil (Autor) Outra

Revista

Título: RAIRO - Theoretical Informatics and Applications

Vol. 42

Páginas: 395-414

ISSN: 0988-3754

Editora: EDP Sciences

Indexação

ISI Web of Knowledge - 10 Citações

ISI Web of Science

Scopus - 12 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Matemática

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 20