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

J. C. Birget, S. Margolis, J. Meakin, P. Weil

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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

Original languageAmerican English
Pages (from-to)247-281
Number of pages35
JournalTheoretical Computer Science
Issue number1-2
StatePublished - Jul 6 2000
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


  • Inverse automata
  • PSPACE-completeness
  • Pure subgroups
  • Subgroups of the free group


Dive into the research topics of 'PSPACE-complete problems for subgroups of free groups and inverse finite automata'. Together they form a unique fingerprint.

Cite this