Let $F$ be a free group of finite rank. We say that the monomorphism problem in $F$ is decidable if for any two elements $u$ and $v$ in $F$, there is an algorithm that determines whether there exists a monomorphism of $F$ that sends $u$ to $v$. In this paper we show that the monomorphism problem is decidable and we provide an effective algorithm that solves the problem.
We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.
The congruence subgroup problem for a finitely generated group $Gamma$ asks whether $widehat{Autleft(Gammaright)}to Aut(hat{Gamma})$ is injective, or more generally, what is its kernel $Cleft(Gammaright)$? Here $hat{X}$ denotes the profinite completion of $X$. In this paper we first give two new short proofs of two known results (for $Gamma=F_{2}$ and $Phi_{2}$) and a new result for $Gamma=Phi_{3}$: 1. $Cleft(F_{2}right)=left{ eright}$ when $F_{2}$ is the free group on two generators. 2. $Cleft(Phi_{2}right)=hat{F}_{omega}$ when $Phi_{n}$ is the free metabelian group on $n$ generators, and $hat{F}_{omega}$ is the free profinite group on $aleph_{0}$ generators. 3. $Cleft(Phi_{3}right)$ contains $hat{F}_{omega}$. Results 2. and 3. should be contrasted with an upcoming result of the first author showing that $Cleft(Phi_{n}right)$ is abelian for $ngeq4$.
We prove that the compressed word problem in a group that is hyperbolic relative to a collection of free abelian subgroups is solvable in polynomial time.
We prove that the finitely presentable subgroups of residually free groups are separable and that the subgroups of type $mathrm{FP}_infty$ are virtual retracts. We describe a uniform solution to the membership problem for finitely presentable subgroups of residually free groups.
The aim of this short note is to provide a proof of the decidability of the generalized membership problem for relatively quasi-convex subgroups of finitely presented relatively hyperbolic groups, under some reasonably mild conditions on the peripheral structure of these groups. These hypotheses are satisfied, in particular, by toral relatively hyperbolic groups.