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

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

doi:10.1016/S0304-3975(98)00225-4

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 journal › Article › peer-review

27 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	247-281
Number of pages	35
Journal	Theoretical Computer Science
Volume	242
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(98)00225-4
State	Published - Jul 6 2000
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

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

Access to Document

10.1016/S0304-3975(98)00225-4

Cite this

@article{db58475d3958420c87368baee99ce0c3,

title = "PSPACE-complete problems for subgroups of free groups and inverse finite automata",

abstract = "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).",

keywords = "Inverse automata, PSPACE-completeness, Pure subgroups, Subgroups of the free group",

author = "Birget, {J. C.} and S. Margolis and J. Meakin and P. Weil",

note = "Funding Information: ∗Corresponding author. E-mail address: [email protected] (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.",

year = "2000",

month = jul,

day = "6",

doi = "10.1016/S0304-3975(98)00225-4",

language = "English (US)",

volume = "242",

pages = "247--281",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

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: [email protected] (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 - 10.1016/S0304-3975(98)00225-4

DO - 10.1016/S0304-3975(98)00225-4

M3 - Article

AN - SCOPUS:0001406323

SN - 0304-3975

VL - 242

SP - 247

EP - 281

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this