Abstract
We investigate the solution and the complexity of algorithmic problems on finitely generated subgroups of free groups. Margolis and Meakin showed how a finite inverse monoid Synt(H) can be canonically and effectively associated to such a subgroup H. We show that H is pure (closed under radical) if and only if Synt(H) is aperiodic. We also show that testing for this property for H is PSPACE-complete. In the process, we show that certain problems about finite automata, which are PSPACE-complete in general, remain PSPACE-complete when restricted to injective and inverse automata — whereas they are known to be in NC for permutation automata.