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

J.C. BIRGET, S. MARGOLIS, J. MEAKIN & P. Weil

IBP-Litp 1996/39: Rapport de Recherche Litp / Litp research reports
32 pages - Décembre/December 1996 - Document en anglais.

Titre / Title: PSPACE - complete problems for subgroups of free groups and inverse finite automata

Résumé : Nous étudions la complexité de certains problèmes algorithmiques sur les sous-groupes finiment engendrés des groupes libres. Margolis et Meakin ont montré qu'on peut associer de façon canonique et effective à un tel sous-groupe H un monoïde fini Synt(H). Nous montrons ici que H est pur (c'est-à-dire fermé par radical) si et seulement si Synt(H) est apériodique. Nous montrons aussi que la décision de la pureté de H est un problème PSPACE-complet. Au passage, 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 à des automates injectifs ou inversifs (avec un seul état acceptant), alors qu'on sait qu'ils sont dans NC pour des automates de permutation (avec un seul état acceptant).

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

Publications internes Litp 1996 / Litp research reports 1996