PSPACE-completeness of certain algorithmic problems on the subgroups of free groups

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

IBP-Litp 1994/23: Rapport de Recherche Litp / Litp research reports
13 pages - Décembre/December 1994 - Document en anglais.

Titre / Title: PSPACE-completeness of certain algorithmic problems on the subgroups of free groups

Résumé : Nous résolvons certains problèmes algorithmiques sur les sous-groupes finiment engendrés du groupe libre et nous étudions leur complexité. Margolis et Meakin ont montré comment un monoïde inversif fini S(H) peut être associé canoniquement et effectivement à un tel sous-groupe H. Nous montrons que H est pur (fermé par radical) si et seulement si S(H) est apériodique. Nous montrons aussi que la vérification de cette propriété de H est un problème PSPACE-complet. Au cours de la preuve, nous montrons que certains problèmes sur les automates finis, qui sont PSPACE-complets en général, restent PSPACE-complets lorsqu'on les restreint aux automates injectifs ou inversifs, alors que l'on sait qu'ils sont dans NC pour les automates de permutation.

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

Publications internes Litp 1994 / Litp research reports 1994