Page d'accueil du CNRS Page d'accueil de Paris Diderot Page d'accueil du LIAFA
LIAFA
Laboratoire d'Informatique Algorithmique: Fondements et Applications
CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 7014
75205 Paris Cedex 13 - Tél: +33(0)1.57.27.92.56 - Fax: +33(0)1.57.27.94.09
Page d'accueil de la fondation Sciences Mathématiques de Paris Page d'accueil de FRMPC
   Staff      Contact      How to get to LIAFA      Teaching      Webmail   


Version française

Research reports

  • 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
  • Summary:


     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
    PostScript format
    pdf format

 
 ©  LIAFA 1995, Last updating: 2013, May webmestre[at]liafa.univ-paris-diderot.fr