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$\left(F\right)$ - rank$\left(H\right)$, which often makes a significant change.

In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal’cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general case. Another...

Let be a pseudovariety of finite groups such that free groups are residually , and let φ: F(A) → F(B) be an injective morphism between finitely generated free groups. We characterize the situations where the continuous extension φ' of φ between the pro- completions of F(A) and F(B) is also injective. In particular, if is extension-closed, this is the case if and only if φ(F(A)) and its pro- closure in F(B) have the same rank. We examine a number of situations where the injectivity of φ' can be...

In a previous paper, the authors studied the polynomial closure of
a variety of languages and gave an algebraic counterpart, in terms
of Mal'cev products, of this operation. They also formulated a
conjecture about the algebraic counterpart of the boolean closure
of the polynomial closure – this operation corresponds to
passing to the upper level in any concatenation hierarchy.
Although this conjecture is probably true in some particular
cases, we give a counterexample in the general case....

We revisit the problem of deciding whether a finitely generated
subgroup is a free factor of a given free group . Known
algorithms solve this problem in time polynomial in the sum of the
lengths of the generators of and exponential in the rank of
. We show that the latter dependency can be made exponential
in the rank difference rank - rank, which often makes a
significant change.

Download Results (CSV)