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

被引：25

作者：

Birget, JC

Margolis, S

Meakin, J

Weil, P

机构：

[1] Univ Bordeaux 1, LaBRI, F-33405 Talence, France

[2] Univ Nebraska, Dept Math, Lincoln, NE 68588 USA

[3] Bar Ilan Univ, Dept Comp Sci, IL-52900 Ramat Gan, Israel

[4] Univ Nebraska, Dept Comp Sci, Lincoln, NE 68588 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2000年 / 242卷 / 1-2期

基金：

美国国家科学基金会;

关键词：

PSPACE-completeness; subgroups of the free group; inverse automata; pure subgroups;

D O I：

10.1016/S0304-3975(98)00225-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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). (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：247 / 281

页数：35

共 26 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] ON THE COMPLEXITY OF INTERSECTION AND CONJUGACY PROBLEMS IN FREE GROUPS [J].