- Year of publication: 1996
- Authors: J.C. BIRGET, S. MARGOLIS, J. MEAKIN & P. WEIL
- Title: Complete problems for subgroups of free groups and inverse finite automata
We investigate the complexity of algorithmic problems on finitely generated subgroups of the free group. 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 PSPACEcomplete 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).
- Complete report:
PostScript file compressed with gzip