𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by J.-C. Birget; S. Margolis; J. Meakin; P. Weil

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
384 KB
Volume
242
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We investigate the complexity of algorithmic problems on ÿnitely generated subgroups of free groups. Margolis and Meakin showed how a ÿnite monoid Synt(H ) can be canonically and e ectively 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 ÿnite 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).

📜 SIMILAR VOLUMES

The uniform word problem for groups and
The uniform word problem for groups and finite Rees quotients of E-unitary inverse semigroups
✍ Benjamin Steinberg 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 133 KB

If C is a class of groups closed under taking subgroups, we show that the decidability of the uniform word problem for C is implied by the decidability of the membership problem for the class of finite Rees quotients of E-unitary inverse semigroups with maximal group image in C. The converse is show