Portal de Periódicos da CAPES

PSPACE-complete problems for subgroups of free groups and inverse finite automata

2000; Elsevier BV; Volume: 242; Issue: 1-2 Linguagem: Inglês

10.1016/s0304-3975(98)00225-4

1879-2294

Jean-Camille Birget, Samuel Margolis, John Meakin, Pascal Weil,

Finite Group Theory Research

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).