Group Independence (GI)

Input

Let $S$ be a finite set and $F$ be the free group generated by $S$. Let $\overline{S} = \{s, s^{-1} \mid s \in S\}$, where $s^{-1}$ denotes the inverse of $s$. Let $\overline{S}^\ast$ denote the set of all finite words over $\overline{S}$. Let $U = \{u_1, \ldots, u_m\} \subseteq \overline{S}^\ast$, where $m \in \N$.

Problem

Is $U$ independent?

Definitions

Set $U$ is independent if each $x \in \langle U \rangle$ has a unique freely reducible representation. A word $w$ is freely reducible if it contains no segment of the form $ss^{-1}$ or $s^{-1}s$.

Status

$\P$-complete (Avenhaus and Madlener [1]).

Remarks

A variant of the Nielsen reduction algorithm can be used to show the problem is in $\P$. The reduction to show hardness is from an arbitrary polynomial time Turing machine [1].