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

TY - JOUR

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

AU - Birget, J. C.

AU - Margolis, S.

AU - Meakin, J.

AU - Weil, P.

N1 - Funding Information: ∗Corresponding author. E-mail address: pascal.weil@labri.u-bordeaux.fr (P. Weil). 1The rst three authors were supported by NSF Grant 92-03981. The fourth author was supported by GdR-PRC AMI. All four authors were supported by the Center for Communication and Information Sciences, University of Nebraska-Lincoln.

PY - 2000/7/6

Y1 - 2000/7/6

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

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

KW - Inverse automata

KW - PSPACE-completeness

KW - Pure subgroups

KW - Subgroups of the free group

UR - http://www.scopus.com/inward/record.url?scp=0001406323&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001406323&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/S0304-3975(98)00225-4

DO - https://doi.org/10.1016/S0304-3975(98)00225-4

M3 - Article

SN - 0304-3975

VL - 242

SP - 247

EP - 281

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -