Abstract
We investigate the complexity of algorithmic problems on finitely generated subgroups of free groups. Margolis and Meakin showed how a finite monoid
Synt(H)
can be canonically and effectively associated with such a subgroup
H. We show that
H is pure (that is, closed under radical) if and only if
Synt(H)
is aperiodic. We also show that testing for this property of
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 (with single accept state), whereas they are known to be in NC for permutation automata (with single accept state).