direct products with \(\mathbb {Z}\) .
Acyclic Automata
In the proofs for the upper bound as well as the lower bound in Theorem REF 
we employ the membership problem for acyclic automata, which has already been studied in connection with
the knapsack and subset sum problem [1]}, [2]}.
We define a finite automaton as a tuple \(\mathcal {A} = (Q,\Sigma , \Delta ,q_0, q_f)\) , where \(Q\)  is a finite set of states, \(\Sigma \)  is the input
alphabet, \(q_0 \in Q\)  is the initial state, \(q_f \in Q\)  is the final state, and
\(\Delta \subseteq Q \times \Sigma ^* \times Q\)  is a finite set of transitions.
The language accepted by
\(\mathcal {A}\)  is denoted with \(L(\mathcal {A})\) . An acyclic automaton is
a finite automaton \(\mathcal {A} = (Q,\Sigma , \Delta , q_0, q_f)\)  such that the
relation \(\lbrace  (p,q) \mid \exists w \in \Sigma ^* : (p,w,q) \in \Delta \rbrace \)  is
acyclic.
For a graph group \(\mathbb {G}(A,I)\)  the membership problem for acyclic automata
is the following computational problem:
Input: An acyclic automaton \(\mathcal {A}\)  over the input alphabet \(A \cup A^{-1}\) .
Question: Is there a word \(w \in L(\mathcal {A})\)  such that \(w=1\)  in \(\mathbb {G}(A,I)\) ?
In order to show the upper bound in logcfl-completeness, we
reduce knapsack for \(\mathbb {G}(A,I)\)  with \((A,I)\)  a transitive forest to
the membership problem for acyclic automata for \(\mathbb {G}(A,I)\)  (note that for subset sum
this reduction is obvious). Then, we
apply the following thm-acyclic-logcfl. From work of Frenkel,
Nikolaev, and Ushakov [1]}, it follows that the membership problem for acyclic automata
is in \(\mathsf {P}\) . We strengthen this to \(\mathsf {LogCFL}\) :
Proposition 6.2 
If \((A,I)\)  is a transitive forest, then the membership problem for acyclic automata over \(\mathbb {G}(A,I)\)  is in \(\mathsf {LogCFL}\) .

The proof of thm-acyclic-logcfl uses the following lemma:
Lemma 6.3 
For every transitive forest \((A,I)\)  with the associated graph group \(G = \mathbb {G}(A,I)\) 
there is a deterministic AuxPDA \(\mathcal {P}(G)\)  with input alphabet \(A^{\pm 1}\)  and the following properties:

In each step, the input head for \(\mathcal {P}(G)\)  either does not move, or moves one step to the right.

If the input word is equal to 1 in \(G\) , then \(\mathcal {P}(G)\)  terminates in the distinguished
state \(q_1\)  with empty stack. Let us call this state the 1-state of \(\mathcal {P}(G)\) .

If the input word is not equal to 1 in \(G\) , then \(\mathcal {P}(G)\)  terminates
in a state different from \(q_1\)  (and the stack is not necessarily empty).


We construct the AuxPDA \(\mathcal {P}(G)\)  by induction over the structure of the group \(G\) . For this, we consider
the three cases that \(G = 1\) , \(G = G_1 * G_2\) , and \(G = \mathbb {Z} \times G^{\prime }\) . The case that
\(G = 1\)  is of course trivial.
Case \(G = \mathbb {Z} \times G^{\prime }\) . We have already constructed the AuxPDA \(\mathcal {P}(G^{\prime })\) .
The AuxPDA \(\mathcal {P}(G)\)  simulates the AuxPDA \(\mathcal {P}(G^{\prime })\) 
on the generators of \(G^{\prime }\) . Moreover, it stores the current value of the \(\mathbb {Z}\) -component in binary notation
on the work tape. If the input word has length \(n\) , then \(O(\log n)\)  bits are sufficient for this. At the end,
\(\mathcal {P}(G)\)  goes into its 1-state if and only if \(\mathcal {P}(G^{\prime })\)  is in its 1-state
(which implies that the stack will be empty) and the \(\mathbb {Z}\) -component is zero.
Case \(G = G_1 * G_2\) . For \(i \in \lbrace 1,2\rbrace \) ,
we have already constructed the AuxPDA \(\mathcal {P}_i = \mathcal {P}(G_i)\) . Let
\(A_i^{\pm 1}\)  be its input alphabet, which is a monoid generating set for \(G_i\) .
Consider now an input word \(w \in (A_1^{\pm 1} \cup A_2^{\pm 1})^*\) .
Let us assume that \(w = u_1 v_1 u_2 v_2 \cdots u_k v_k\)  with \(u_i \in (A_1^{\pm 1})^+\)  and \(v_i \in (A_2^{\pm 1})^+\)  (other cases
can be treated analogously). The AuxPDA \(\mathcal {P}(G)\)  starts with empty stack and simulates the AuxPDA
\(\mathcal {P}_1\)  on the prefix \(u_1\) . If it turns out that \(u_1 = 1\)  in \(G_1\)  (which means that \(\mathcal {P}_1\)  is
in its 1-state) then the stack will be empty and the AuxPDA \(\mathcal {P}(G)\) 
continues with simulating \(\mathcal {P}_2\)  on \(v_1\) . On the other hand, if \(u_1 \ne 1\)  in \(G_1\) , then \(\mathcal {P}(G)\) 
pushes the state together with the work tape content of \(\mathcal {P}_1\)  reached after reading \(u_1\)  on the stack (on top of
the final stack content of \(\mathcal {P}_1\) ). This allows \(\mathcal {P}(G)\)  to resume the computation of \(\mathcal {P}_1\)  later. Then \(\mathcal {P}(G)\) 
continues with simulating \(\mathcal {P}_2\)  on \(v_1\) .
The computation of \(\mathcal {P}(G)\)  will continue in this way. More precisely, if after reading \(u_i\)  (resp. \(v_i\)  with \(i < k\) ) the
AuxPDA \(\mathcal {P}_1\)  (resp. \(\mathcal {P}_2\) ) is in its 1-state then either

the stack is empty or

the top part of the stack is of the form \(s q t\)  (\(t\)  is the top), where \(s\)  is a stack content of \(\mathcal {P}_2\) 
(resp. \(\mathcal {P}_1\) ), \(q\)  is a state of \(\mathcal {P}_2\) 
(resp. \(\mathcal {P}_1\) ) and \(t\)  is a work tape content of \(\mathcal {P}_2\) 
(resp. \(\mathcal {P}_1\) ).

In case (i), \(\mathcal {P}(G)\)  continues with the simulation of \(\mathcal {P}_2\) 
(resp. \(\mathcal {P}_1\) ) on the word \(v_i\)  (resp. \(u_{i+1}\) ) in the initial configuration.
In case (ii), \(\mathcal {P}(G)\)  continues with the simulation of \(\mathcal {P}_2\) 
(resp. \(\mathcal {P}_1\) ) on the word \(v_i\)  (resp. \(u_{i+1}\) ), where the simulation is started with
stack content \(s\) , state \(q\) , and work tape content \(t\) . On the other hand, if after reading \(u_i\)  (resp. \(v_i\)  with \(i < k\) ) the
AuxPDA \(\mathcal {P}_1\)  (resp. \(\mathcal {P}_2\) ) is not in its 1-state then \(\mathcal {P}(G)\)  pushes on the stack the state
and work tape content of \(\mathcal {P}_1\)  reached after its simulation on \(u_i\) .
This concludes the description of the AuxPDA \(\mathcal {P}(G)\) . It is clear that \(\mathcal {P}(G)\)  has the properties
stated in the lemma.
We can now prove thm-acyclic-logcfl:
Fix the graph group \(G = \mathbb {G}(A,I)\) ,
where \((A,I)\)  is a transitive forest. An AuxPDA for the membership problem for acyclic automata
guesses a path in the input automaton \(\mathcal {A}\)  and thereby simulates the AuxPDA \(\mathcal {P}(G)\)  from Lemma REF .
If the final state of the input automaton \(\mathcal {A}\)  is reached while the AuxPDA \(\mathcal {P}(G)\)  is in the accepting state \(q_1\) ,
then the overall AuxPDA accepts. It is important that the AuxPDA \(\mathcal {P}(G)\)  works one-way since
the guessed path in \(\mathcal {A}\)  cannot be stored in logspace. This implies that the AuxPDA cannot reaccess
the input symbols that already have been processed. Also note that the AuxPDA
is logspace bounded and polynomially time bounded since \(\mathcal {A}\) 
is acyclic.

Bounds on knapsack solutions
As mentioned above, we reduce for graph groups \(\mathbb {G}(A,I)\)  with \((A,I)\)  a transitive forest
the knapsack problem to the membership problem for acyclic automata.
To this end, we show that every positive knapsack instance has a
polynomially bounded solution. The latter is the most involved proof in our
paper.
Frenkel, Nikolaev, and Ushakov [1]} call groups with this
property polynomially bounded knapsack groups and show that this class
is closed under taking free products. However, it is not clear if direct
products with \(\mathbb {Z}\)  also inherit this property and we leave this question open.
Hence, we are looking for a property that yields polynomial-size solutions and
is passed on to free products and to direct products with \(\mathbb {Z}\) . It is known
that the solution sets are always semilinear. If \((A,I)\)  is a transitive
forest, this follows from a more general semilinearity property of rational
sets [5]} and for arbitrary graph groups, this was shown in
[6]}. Note that it is not true that the solution sets alwas have
polynomial-size semilinear representations. This already fails in the case of \(\mathbb {Z}\) :
The equation \(\mathsf {x}_1+\cdots +\mathsf {x}_{k}=k\)  has \(\binom{2k-1}{k}\ge 2^k\)  solutions.
We will show here that the solution sets have semilinear representations
where every occuring number is bounded by a polynomial.
For a vector \(x=(x_1,\ldots ,x_k)\in \mathbb {Z}^k\) , we define the norm
\(\Vert x\Vert =\max \lbrace |x_i| \mid i\in [1,k]\rbrace .\) 
For a subset \(T\subseteq \mathbb {N}^k\) , we write \(T^\oplus \)  for
the smallest subset of \(\mathbb {N}^k\)  that contains 0 and is closed under addition.
A subset \(S\subseteq \mathbb {N}^k\)  is called linear if there is a vector
\(x\in \mathbb {N}^k\)  and a finite set \(F\subseteq \mathbb {N}^k\)  such that \(S=x+F^\oplus \) . Note
that a set is linear if and only if it can be written as \(x+A\mathbb {N}^t\)  for some
\(x\in \mathbb {N}^k\)  and some matrix \(A\in \mathbb {N}^{k\times t}\) . Here, \(A\mathbb {N}^t\)  denotes the set
of all vectors \(Ay\)  for \(y\in \mathbb {N}^t\) . A semilinear set is a finite union
of linear sets. If \(S=\bigcup _{i=1}^n x_i+F_i^\oplus \)  for
\(x_1,\ldots ,x_n\in \mathbb {N}^k\)  and finite sets \(F_1,\ldots ,F_n\subseteq \mathbb {N}^k\) , then the
tuple \((x_1,F_1,\ldots ,x_n,F_n)\)  is a semilinear representation of \(S\) 
and the magnitude of this representation is defined as the maximum of
\(\Vert y\Vert \) , where \(y\)  ranges over all elements of \(\bigcup _{i=1}^n \lbrace x_i\rbrace \cup F_i\) . The magnitude of a semilinear set \(S\)  is the smallest magnitude
of a semilinear representation for \(S\) .
Definition 6.4 A group \(G\)  is called knapsack tame if there is a polynomial \(p\)  such
that for every exponent equation \(h_0 g_1^{\mathsf {x}_1}h_1g_2^{\mathsf {x}_2}h_2\cdots g_n^{\mathsf {x}_k}h_k=1\)  of size \(n\)  with pairwise distinct variables
\(\mathsf {x}_1,\ldots ,\mathsf {x}_k\) , the set \(S\subseteq \mathbb {N}^k\)  of solutions is semilinear
of magnitude at most \(p(n)\) .

Observe that although the size of an exponent equation may depend on the chosen
generating set of \(G\) , changing the generating set increases the size only by a
constant factor. Thus, whether or not a group is knapsack tame is independent of
the chosen generating set.
Theorem 6.5 
If \((A,I)\)  is a transitive forest, then \(\mathbb {G}(A,I)\)  is knapsack tame.

Note that tforest-tame implies in particular that every solvable
exponent equation with pairwise distinct variables has a polynomially bounded solution.
tforest-tame and thm-acyclic-logcfl easily yield the upper bound
in logcfl-completeness, see tforest-logcfl-membership.
We prove tforest-tame by showing that knapsack tameness transfers from groups \(G\) 
to \(G\times \mathbb {Z}\)  (tame-directz) and from \(G\)  and \(H\)  to \(G*H\) 
(tameness-free-preserved). Since the trivial group is obviously knapsack
tame, the inductive characterization of groups \(\mathbb {G}(A,I)\)  for transitive
forests \((A,I)\)  immediately yields tforest-tame.

Tameness of direct products with \(\mathbb {Z}\)
In this tame-directz-section, we show the following.
Proposition 6.6 
If \(G\)  is knapsack tame, then so is \(G\times \mathbb {Z}\) .


Linear Diophantine equations
Vectors will be column vectors in this section. For a vector \(x \in \mathbb {Z}^k\)  we denote
with \(x^T\)  the corresponding row vector.
We employ a result of
Pottier [7]}, which bounds the norm of minimal non-negative
solutions to a linear Diophantine equation. Let \(A\in \mathbb {Z}^{k\times m}\)  be an
integer matrix where \(a_{ij}\)  is the entry of \(A\)  at row \(i\)  and column \(j\)  and
let \(x\in \mathbb {Z}^m\)  be a vector with entries \(x_i\) . We will use the following norms:
\(\Vert A\Vert _{1,\infty } &=& \max _{i\in [1,k]}(\sum _{j\in [1,m]} |a_{ij}|), \\\Vert A\Vert _{\infty ,1} &=& \max _{j\in [1,m]} (\sum _{i\in [1,k]} |a_{ij}|), \\\Vert A\Vert _{\infty } &=& \max _{i\in [1,k], j\in [1,m]} |a_{ij}|, \\\Vert x\Vert _1 &=& \sum _{i=1}^m |x_i| .\) 
Recall that \(\Vert x\Vert =\max _{i\in [1,m]} |x_i|\) . A non-trivial solution \(x\in \mathbb {N}^m\setminus \lbrace 0\rbrace \)  to
the equation \(Ax=0\)  is minimal if there is no \(y\in \mathbb {N}^m\setminus \lbrace 0\rbrace \)  with \(Ay=0\)  and
\(y\le x\) , \(y\ne x\) . Here \(y \le x\)  means that \(y_i \le x_i\)  for all \(i \in [1,m]\) .
The set of all solutions clearly forms a submonoid of
\(\mathbb {N}^m\) . Let \(r\)  be the rank of \(A\) .
Theorem 6.7 (Pottier [7]}) 
Each non-trival minimal solution \(x \in \mathbb {N}^m\)  to \(Ax=0\)  satisfies
\(\Vert x\Vert _1\le (1+\Vert A\Vert _{1,\infty })^r\) .

We only need pottier for the case that \(A\)  is a row vector \(u^T\)  for \(u \in \mathbb {Z}^k\) .
Corollary 6.8 
Let \(u \in \mathbb {Z}^k\) . Each
non-trival minimal solution \(x \in \mathbb {N}^k\)  to \(u^T x=0\)  satisfies
\(\Vert x\Vert _1\le 1+\Vert u\Vert _1\) .

By applying pottier to the row vector \((u^T, -b)\)  for \(b \in \mathbb {Z}\) , it is easy to
deduce that for each \(x\in \mathbb {N}^k\)  with \(u^T x=b\) , there is a \(y\in \mathbb {N}^k\)  with \(u^T y=b\) ,
\(y\le x\) , and \(\Vert y\Vert _1\le 1+\Vert  \binom{u}{b}\Vert _1 = 1+ \Vert u\Vert _1 + |b|\) .
We reformulate c-pottier as follows.
Lemma 6.9 
Let \(u \in \mathbb {Z}^k\)  and \(b \in \mathbb {Z}\) .
Then the set
\(\lbrace x\in \mathbb {N}^k \mid u^T x=b\rbrace \)  admits a decomposition
\(\lbrace  x\in \mathbb {N}^k \mid u^T x=b \rbrace  = \bigcup _{i=1}^{s} c_i + C\mathbb {N}^t\) ,
where \(c_i\in \mathbb {N}^k\)  and \(C\in \mathbb {N}^{k\times t}\)  with \(\Vert c_i\Vert _1\)  and \(\Vert C\Vert _{\infty ,1}\)  bounded by \(1+\Vert u\Vert _1+|b|\) .

Let \(\lbrace c_1,\ldots ,c_s\rbrace \)  be the set of minimal solutions of \(u^Tx=b\) . Then, as explained above, c-pottier
yields \(\Vert c_i\Vert _1\le 1+ \Vert u\Vert _1 + |b|\) .
Moreover, let \(C\in \mathbb {N}^{k\times t}\)  be the matrix whose columns are the non-trivial minimal solutions of
\(u^T x=0\) . Then we have \(\Vert C\Vert _{\infty ,1} \le 1+\Vert u\Vert _1\) .
This clearly yields the desired decomposition.
The problem is that we want to apply pottier-reform in a situation where we
have no bound on \(\Vert u\Vert _1\) , but only one on \(\Vert u\Vert \) .
The following lemma yields such a bound.
Lemma 6.10 
If \(u\in \mathbb {Z}^k\)  and \(b\in \mathbb {Z}\)  with \(\Vert u\Vert ,|b|\le M\) ,
then we have a decomposition
\(\lbrace x\in \mathbb {N}^k \mid u^Tx=b \rbrace  = \bigcup _{i=1}^{s} c_i + C\mathbb {N}^t \) 
where \(\Vert c_i\Vert _1, \Vert C\Vert _{\infty ,1} \le 1+(M+2)M\) .

Write \(u^T=(b_1,\ldots ,b_k)\)  and consider the row vector \(v^T = (b^{\prime }_1,\ldots ,b^{\prime }_{2M+1})\) , \(v \in \mathbb {Z}^{2M+1}\) , with entries \(b^{\prime }_i = i-(M+1)\) .
Thus, we have
\( v^T = (b^{\prime }_1,\ldots ,b^{\prime }_{2M+1})=(-M,-M+1,\ldots ,-1,0,1,\ldots ,M) .\) 
Moreover, define the matrix \(S = (s_{ij}) \in \mathbb {N}^{(2M+1)\times k}\)  with
\( s_{ij} = {\left\lbrace \begin{array}{ll} 1 & \text{if $b_j=b^{\prime }_i$,} \\ 0 & \text{otherwise.} \end{array}\right.} \) 
Then clearly \(u=v^T S\)  and \(\Vert v\Vert _1 =(M+1)M\) . Furthermore, observe that
we have \(\Vert Sx\Vert _1=\Vert x\Vert _1\)  for every \(x\in \mathbb {N}^k\)  and that for each \(y\in \mathbb {N}^{2M+1}\)  the set
\( T_y = \lbrace  x\in \mathbb {N}^k \mid Sx=y\rbrace  \) 
is finite. According to pottier-reform, we can write
\( \lbrace x\in \mathbb {N}^{2M+1} \mid v^T x=b \rbrace  = \bigcup _{i=1}^{s^{\prime }} c^{\prime }_i+C^{\prime }\mathbb {N}^{t^{\prime }} \) 
where \(\Vert c^{\prime }_i\Vert _1, \Vert C^{\prime }\Vert _{\infty ,1} \le 1+ (M+1)M + M = 1+(M+2)M\) .
Let \(\lbrace  c_1,\ldots ,c_s\rbrace \)  be the union of all sets \(T_{c^{\prime }_i}\) 
for \(i\in [1,s^{\prime }]\)  and let \(C\in \mathbb {N}^{k\times t}\)  be the matrix whose columns
comprise all \(T_v\)  where \(v\in \mathbb {N}^{2M+1}\)  is a column of \(C^{\prime }\) . Since
we have \(\Vert Sx\Vert _1=\Vert x\Vert _1\)  for \(x\in \mathbb {N}^k\) , the vectors \(c_i\)  obey the same bound as the
vectors \(c^{\prime }_i\) , meaning \(\Vert c_i\Vert _1\le 1+(M+2)M\) . By the same argument, we have
\(\Vert C\Vert _{\infty ,1}\le \Vert C^{\prime }\Vert _{\infty ,1}\le 1+(M+2)M\) . It remains to be shown that
the equality from the sol-decomp-onedim holds.
Suppose \(u^T x=b\) . Then \(v^TSx=b\)  and hence \(Sx=c^{\prime }_i+C^{\prime }y\)  for some \(y\in \mathbb {N}^{t^{\prime }}\) .
Observe that if \(Sz=p+q\)  for \(p,q \in \mathbb {N}^{2M+1}\) , then \(z\)  decomposes as \(z=p^{\prime }+q^{\prime }\) , \(p^{\prime },q^{\prime } \in \mathbb {N}^k\) , so that \(Sp^{\prime }=p\)  and
\(Sq^{\prime }=q\) . Therefore, we can write \(x=x_0+\cdots +x_n\)  with \(Sx_0=c^{\prime }_i\)  and
\(Sx_j\)  is some column of \(C^{\prime }\)  for each \(j\in [1,n]\) . Hence, \(x_0=c_r\)  for some \(r\in [1,s]\)  and for
each \(j\in [1,n]\) , \(x_j\)  is a column of \(C\) . This proves \(x\in c_r + C\mathbb {N}^t\) .
On the other hand, the definition of \(c_1,\ldots ,c_s\)  and \(C\)  implies that
for each column \(v\)  of \(C\) , \(Sv\)  is a column of \(C^{\prime }\) . Moreover, for each
\(i\in [1,s]\) , there is a \(j\in [1,s^{\prime }]\)  with \(Sc_i=c^{\prime }_j\)  and thus
\(Sc_i+SC\mathbb {N}^t\subseteq c^{\prime }_j+C^{\prime }\mathbb {N}^{t^{\prime }}\) . Therefore
\( u^T(c_i+C\mathbb {N}^t) =v^TS(c_i+C\mathbb {N}^t)\subseteq v^T(c^{\prime }_j+C^{\prime }\mathbb {N}^{t^{\prime }}) \) 
and the latter set contains only \(b\)  because of sol-decomp-onedim-step.
Lemma 6.11 
Let \(S\subseteq \mathbb {N}^k\)  be a semilinear set of magnitude \(M\)  and \(u\in \mathbb {Z}^k\) , \(b\in \mathbb {Z}\) 
with \(\Vert u\Vert , |b| \le m\) . Then \(\lbrace  x\in S \mid u^T x=b \rbrace \) 
is a semilinear set of magnitude at most \((kmM)^d\)  for some constant \(d\) .

Let \(T=\lbrace x\in \mathbb {N}^k \mid u^Tx=b\rbrace \) . We may assume that \(S\)  is linear of magnitude
\(M\) , because if \(S=L_1\cup \cdots \cup L_n\) , then \(S\cap T=(L_1\cap T)\cup \cdots \cup (L_n\cap T)\) .
Write \(S=a+A\mathbb {N}^n\)  with \(a\in \mathbb {N}^k\)  and \(A\in \mathbb {N}^{k\times n}\) , where
\(\Vert a\Vert \le M\)  and \(\Vert A\Vert _\infty \le M\) . Consider the set \(U=\lbrace x\in \mathbb {N}^n \mid u^T Ax=b-u^T a\rbrace \) . Note that \(u^T A\in \mathbb {Z}^{1\times n}\)  and
\( \Vert u^TA\Vert  \le k\cdot \Vert u\Vert  \cdot \Vert A\Vert _\infty \le kmM, \) 
\( |b-u^Ta| \le m+k\cdot \Vert u\Vert  \cdot \Vert a\Vert \le m+kmM. \) 
According to sol-decomp-onedim, we can write \(U=\bigcup _{i=1}^sc_i+C\mathbb {N}^t\)  where \(\Vert c_i\Vert _1\)  and \(\Vert C\Vert _{\infty ,1}\)  are at most
\(1+ (m+kmM)(m+kmM+2)\) . Observe that
\( a+AU = \bigcup _{i=1}^s a+Ac_i+AC\mathbb {N}^t \) 
and
\( \Vert a+Ac_i\Vert \le \Vert a\Vert  + \Vert A\Vert _\infty \cdot \Vert c_i\Vert _1 \le 2M + M (m+kmM)(m+kmM+2) , \) 
\( \Vert  AC \Vert _{\infty } \le \Vert A\Vert _\infty \cdot \Vert C\Vert _{\infty ,1} \le M + M (m+kmM)(m+kmM+2). \) 
Finally, note that \(S\cap T=a+AU\) .
We are now ready to prove tame-directz.
Suppose \(G\)  is knapsack tame with polynomial \(\bar{p}\) .
Let
\(h_0g_1^{\mathsf {x}_1}h_1g_2^{\mathsf {x}_2}h_2\cdots g_k^{\mathsf {x}_k}h_k=1 \) 
be an exponent equation of size \(n\)  with pairwise distinct variables
\(\mathsf {x}_1,\ldots ,\mathsf {x}_k\)  and with \(h_0,g_1,h_1,\ldots ,g_k,h_k\in G\times \mathbb {Z}\) . Let
\(h_i=(\bar{h}_i,y_i)\)  for \(i\in [0,k]\)  and \(g_i=(\bar{g}_i,z_i)\)  for \(i\in [1,k]\) .
The exponent equation
\(\bar{h}_0\bar{g}_1^{\mathsf {x}_1}\bar{h}_1\bar{g}_2^{\mathsf {x}_2}\bar{h}_2\cdots \bar{g}_k^{\mathsf {x}_k}\bar{h}_k=1\)  has a semilinear solution set
\(\bar{S}\subseteq \mathbb {N}^k\)  of magnitude at most \(\bar{p}(n)\) . The solution set of
tame-directz-eq1 is
\( S=\lbrace  (x_1,\ldots ,x_k)\in \bar{S} \mid z_1x_1+\cdots +z_kx_k=y \rbrace , \) 
where \(y=-(y_0+\cdots +y_k)\) . Note that \(|z_i|\le n\)  and
\(|y|\le n\) . By semil-intersection, \(S\)  is semilinear of magnitude
\((n^2\bar{p}(n))^d\)  for some constant \(d\)  (recall that \(k\le n\) ).

Tameness of free products
This section is devoted to the proof of the following tameness-free-preserved.
Proposition 6.12 
If \(G_0\)  and \(G_1\)  are knapsack tame, then so is \(G_0*G_1\) .

Let \(G = G_0*G_1\) .
Suppose that for \(i \in \lbrace 0,1\rbrace \) , the group \(G_i\)  is generated by \(A_i\) ,
where w.l.o.g. \(A_i^{-1}=A_i\)  and let \(A=A_0\uplus A_1\) , which generates \(G\) . Recall that every \(g\in G\)  can be
written uniquely as \(g=g_1\cdots g_n\)  where \(n \ge 0\) , \(g_i\in (G_0 \setminus \lbrace 1\rbrace ) \cup (G_1 \setminus \lbrace 1\rbrace )\)  for
each \(i\in [1,n]\)  and where \(g_j\in G_t\)  iff \(g_{j+1}\in G_{1-t}\)  for
\(j\in [1,n-1]\) . We call \(g\)  cyclically reduced if for some
\(t\in \lbrace 0,1\rbrace \) , either \(g_1\in G_t\)  and \(g_n\in G_{1-t}\)  or \(g_1,g_n\in G_t\)  and
\(g_ng_1\ne 1\) . Consider an exponent equation
\( h_0g_1^{\mathsf {x}_1}h_1\cdots g_k^{\mathsf {x}_k}h_k=1, \) 
of size \(n\) , where \(g_i\)  is represented by \(u_i\in A^*\)  for \(i\in [1,k]\)  and
\(h_i\)  is represented by \(v_i\in A^*\)  for \(i\in [0,k]\) . Then clearly
\(\sum _{i=0}^k |v_i|+\sum _{i=1}^k |u_i|\le n\) . Let \(S\subseteq \mathbb {N}^k\)  be the set
of all solutions to tameness-free-expeq. Every word \(w\in A^*\)  has
a (possibly empty) unique factorization into maximal factors from \(A_0^+\cup A_1^+\) , which we call syllables. By \(\Vert w\Vert \) , we denote the number of
syllables of \(w\) . The word \(w\)  is reduced if none of its syllables
represents 1 (in \(G_0\)  resp. \(G_1\) ). We define the maps \(\lambda ,\rho \colon A^+\rightarrow A^+\)  (”rotate left/right”), where for each word \(w\in A^+\)  with its
factorization \(w=w_1\cdots w_m\)  into syllables, we set \(\lambda (w)=w_2\cdots w_mw_1\)  and \(\rho (w)=w_m w_1w_2\cdots w_{m-1}\) .
Consider a word \(w\in A^*\)  and suppose \(w=w_1\cdots w_m\) , \(m \ge 0\) , where for each
\(i\in [1,m]\) , we have \(w_i\in A_j^+\)  for some \(j\in \lbrace 0,1\rbrace \)  (we allow that \(w_i, w_{i+1} \in A_j^+\) ). A
cancellation is a subset \(C\subseteq 2^{[1,m]}\)  that is

a partition: \(\bigcup _{I\in C} I=[1,m]\)  and \(I\cap J=\emptyset \)  for any \(I,J\in C\)  with \(I\ne J\) .

consistent: for each \(I\in C\) , there is an \(i\in \lbrace 0,1\rbrace \)  such that
\(w_j\in A_i^+\)  for all \(j\in I\) .

cancelling: if \(\lbrace i_1,\ldots ,i_\ell \rbrace \in C\)  with
\(i_1<\cdots <i_\ell \) , then \(w_{i_1}\cdots w_{i_\ell }\)  represents 1 in \(G\) .

well-nested: there are no \(I,J\in C\)  with \(i_1,i_2\in I\)  and \(j_1,j_2\in J\)  such that \(i_1<j_1<i_2<j_2\) .

maximal: if \(w_i, w_{i+1} \in A_j^+\)  for \(j\in \lbrace 0,1\rbrace \)  then there is an \(I \in C\)  with \(i,i+1 \in I\) .

Since \(C\)  can be regarded as a hypergraph on \([1,m]\) , the elements of \(C\)  will
be called edges. We have the following simple fact:
Lemma 6.13 Let \(w=w_1\cdots w_m\) , \(m \ge 0\) , where for each
\(i\in [1,m]\) , we have \(w_i\in A_j^+\)  for some \(j\in \lbrace 0,1\rbrace \) .
Then \(w\)  admits a cancellation if and only if it represents 1 in \(G\) .

Assume that \(w\)  representes 1 in the free product \(G\) .
The case \(w = \varepsilon \)  is clear; hence assume that \(w \ne \varepsilon \) .
Then there must
exist a factor \(w_i w_{i+1} \cdots w_j\)  representing 1 in \(G\)  such that
(i) \(w_i w_{i+1} \cdots w_j \in A_k^+\)  for some \(k \in \lbrace 0,1\rbrace \) ,
(ii) either \(i=1\)  or \(w_{i-1} \in A_{1-k}^+\) , and (iii) either \(j=m\)  or \(w_{j+1} \in A_{1-k}^+\) .
The word \(w^{\prime } = w_1 \cdots w_{i-1} w_{j+1}\cdots w_m\)  also represents 1 in \(G\) .
By induction, \(w^{\prime }\)  admits a cancellation \(C^{\prime }\) . Let \(C^{\prime \prime }\)  be obtained from \(C^{\prime }\)  by replacing every
occurrence of an index \(k \ge i\)  in \(C^{\prime }\)  by \(k+j-i+1\) . Then
\(C = C^{\prime \prime } \cup \lbrace  [i,j] \rbrace \)  is a cancellation for \(w\) .
For the other direction let us call a partition \(C \subseteq 2^{[1,m]}\)  a weak cancellation
if it is consistent, cancelling and well-nested (but not necessarily maximal). Then we show by
induction that \(w\)  represents 1 if it has a weak cancellation. So, let \(C\)  be a weak cancellation of \(w \ne \varepsilon \) .
Then there must exist an interval \([i,j] \in C\)  (otherwise
\(C\)  would be not well-nested). Then \(w_i w_{i+1} \cdots w_j\)  represents 1 in \(G\) . Consider the word
\(w^{\prime } = w_1 \cdots w_{i-1} w_{j+1}\cdots w_m\) . Let \(C^{\prime }\)  be obtained from \(C \setminus \lbrace  [i,j] \rbrace \)  by replacing
every occurrence of an index \(k \ge j+1\)  in \(C \setminus \lbrace  [i,j] \rbrace \)  by \(k-j+i-1\) .
Then \(C^{\prime }\)  is a weak cancellation for \(w^{\prime }\) . Hence, \(w^{\prime }\)  represents 1, which implies that \(w\)  represents 1.
Of course, when showing that the solution set of (REF )
has a polynomial magnitude, we may assume that \(g_i\ne 1\)  for any
\(i\in [1,k]\) . Moreover, we lose no generality by assuming that all words \(u_i\) ,
\(i\in [1,k]\)  and \(v_i\) , \(i\in [0,k]\)  are reduced. Furthermore, we may assume
that each \(g_i\)  is cyclically reduced. Indeed, if some \(g_i\)  is not cyclically
reduced, we can write \(g_i=f^{-1}gf\)  for some cyclically reduced \(g\)  and
replace \(h_{i-1}\) , \(g_i\) , and \(h_{i}\)  by \(h_{i-1}f^{-1}\) , \(g=fg_if^{-1}\) , and
\(fh_{i}\) , respectively. This does not change the solution set because
\(h_{i-1}f^{-1}(fg_if^{-1})^{x_i}fh_{i}=h_{i-1}g_i^{x_i}h_i\) . Moreover, if we
do this replacement for each \(g_i\)  that is not cyclically reduced, we increase
the size of the instance by at most \(2|g_1|+\cdots +2|g_k|\le 2n\)  (note that
\(|g|=|g_i|\) ). Applying this argument again, we may even assume that
\(u_i\in A_0^+\cup A_1^+\cup A_0^+A^*A_1^+ \cup A_1^+A^*A_0^+ \) 
for every \(i\in [1,k]\) . Note that \(\lambda \)  and \(\rho \)  are bijections on words of this form.
Consider a solution \((x_1,\ldots ,x_k)\)  to tameness-free-expeq. Then the word
\( w=v_0u_1^{x_1}v_1\cdots u_k^{x_k}v_k \) 
represents 1 in \(G\) . We
factorize each \(v_i\) , \(i\in [0,k]\) , and each \(u_i\) , \(i\in [1,k]\) , into its
syllables. These factorizations define a factorization \(w=w_1\cdots w_m\)  and we
call this the block factorization of \(w\) .
This is the
coarsest refinement of the factorization \(w=v_0u_1^{x_1}v_1\cdots u_k^{x_k}v_k\) 
and of \(w\) 's factorization into syllables.
The numbers \(1, 2, \ldots , m\)  are the blocks of \(w\) .
We fix this factorization \(w = w_1 \cdots w_m\)  for the rest of this section.

Cycles and certified solutions
In the representation \(v_0u_1^{\mathsf {x}_1}v_1\cdots u_k^{\mathsf {x}_k}v_k=1\)  of tameness-free-expeq, the words \(u_1,\ldots ,u_k\) 
are called the cycles. If \(u_i\in A_0^+\cup A_1^+\) , the cycle \(u_i\)  is
said to be simple and otherwise mixed (note that
\(u_i=\varepsilon \)  cannot happen because \(g_i\ne 1\) ).
Let \(p\)  be a block of \(w\) . If \(w_p\)  is contained in
some \(u_i^{x_i}\)  for a cycle \(u_i\) , then \(p\)  is a \(u_i\) -blocks or
block from \(u_i\). If \(w_p\)  is contained in
some \(v_i\) , then \(p\)  is a \(v_i\) -block
or a block from \(v_i\).
Note that if \(C\subseteq 2^{[1,m]}\)  is a cancellation for \(w = w_1 \cdots w_m\)  then
by maximality, for each simple cycle \(u_i\) , all \(u_i\) -blocks are contained in the same edge of \(C\) .
A certified solution is a pair \((x,C)\) , where \(x\)  is a solution to tameness-free-expeq
and \(C\)  is a cancellation of the word \(w\)  as in tameness-free-sol1.
We will also need the following two auxiliary lemmas.
Lemma 6.14 
Let \(C\)  be a cancellation. If \(i,j\)  are two distinct blocks from the same
mixed cycle, then there is no edge \(I\in C\)  with \(i,j\in I\) .

Suppose there is such an \(I\in C\) . Furthermore, assume that \(i\)  and \(j\)  are
chosen so that \(|i-j|\)  is minimal and \(i<j\) . Since \(i,j\in I\) , we have \(w_iw_j\in A_0^+\cup A_1^+\)  by consistency of \(C\) . Hence, by
tameness-free-format, we cannot have \(j=i+1\) .
Therefore there is an \(\ell \in [1,m]\)  with \(i<\ell <j\) . This means there is a \(J\in C\)  with \(\ell \in J\) . By well-nestedness, \(J\subseteq [i,j]\) . Since every
edge in \(C\)  must contain at least two elements, we have \(|J|\ge 2\)  and thus a
contradiction to the minimality of \(|i-j|\) .
An edge \(I\in C\)  is called standard if
\(|I|=2\)  and the two blocks in \(I\)  are from mixed cycles. Intuitively, the
following lemma tells us that in a cancellation, most edges are standard.
Lemma 6.15 
Let \(C\)  be a cancellation and \(u_i\)  be a mixed cycle. Then there are at
most \(n+3k+1\)  non-standard edges \(I\in C\)  containing a \(u_i\) -block.

Let \(N\subseteq C\)  be the set of all non-standard edges \(I\in C\)  that contain a \(u_i\) -block.
Then, each edge \(I\in N\)  satisfies one of the following.

\(I\)  contains a block from some simple cycle. There are at
most \(k\)  such \(I\) .

\(I\)  contains a block from some \(v_j\) , \(j\in [0,k]\) . Since
\(\Vert v_0\Vert +\cdots +\Vert v_k\Vert \le n\) , there are at most \(n\)  such \(I\) .

 \(I\)  contains only blocks from mixed cycles and \(|I|>2\) .

Let \(M\subseteq C\)  be the set of edges of type
tameness-free-nonstandard-mixed. If we can show that \(|M|\le 2k+1\) , then the
tameness-free-nonstandard is proven. Consider the sets
\(M_- &= \lbrace  I\in M \mid \text{$I$ contains a block from a mixed cycle $u_j$, $j<i$} \rbrace , \\M_+ &= \lbrace  I\in M \mid \text{$I$ contains a block from a mixed cycle $u_j$, $j>i$} \rbrace .\) 

We shall prove that \(|M_-\cap M_+|\le 1\)  and that \(|M_+\setminus M_-|\le k\) . By
symmetry, this also means \(|M_-\setminus M_+|\le k\)  and thus \(|M|=|M_- \cup M_+|\le 2k+1\) .
Suppose \(I_1,I_2\in M_-\cap M_+\) , \(I_1\ne I_2\) . Let \(r\in I_1\)  and \(s\in I_2\) 
such that \(r\)  and \(s\)  are blocks from \(u_i\) , say with \(r<s\) . Since \(I_1\in M_+\) , \(I_1\)  contains a block \(r^{\prime }\)  from a mixed cycle \(u_j\) , \(j>i\) . This
means in particular \(s<r^{\prime }\) . By well-nestedness, this implies \(I_2\subseteq [r,r^{\prime }]\) , so that \(I_2\)  cannot contain a block from a mixed cycle \(u_\ell \)  with
\(\ell <i\) , contradicting \(I_2\in M_-\) . Thus, \(|M_-\cap M_+|\le 1\) .
In order to prove \(|M_+\setminus M_-|\le k\) , we need another concept. For each
\(I\in M_+\) , there is a maximal \(j\in [1,k]\)  such that \(u_j\)  is a mixed cycle
and \(I\)  contains a block from \(u_j\) . Let \(\mu (I)=j\) . We will show
\(\mu (I_1)\ne \mu (I_2)\)  for all \(I_1,I_2\in M_+\setminus M_-\) , \(I_1\ne I_2\) . This
clearly implies \(|M_+\setminus M_-|\le k\) .
Suppose \(I_1,I_2\in M_+\setminus M_-\) , \(I_1\ne I_2\) , with \(\mu (I_1)=\mu (I_2)\) .
Let \(j=\mu (I_1)=\mu (I_2)\) . Let \(r\)  be a block from \(u_i\)  contained in \(I_1\) 
and let \(r^{\prime }\)  be a block from \(u_i\)  contained in \(I_2\) . (Recall that those
exist because \(I_1,I_2\in M\) .) Without loss of generality, assume \(r<r^{\prime }\) .
Moreover, let \(s\)  be a block from \(u_j\)  contained in \(I_1\)  and let \(s^{\prime }\) 
be a block from \(u_j\)  contained in \(I_2\) . Thus, we have \(r < r^{\prime } < s^{\prime }\) .
However, we have \(|I_1|>2\) , meaning \(I_1\)  contains a block \(p\)  other than
\(r\)  and \(s\) . Since an edge cannot contain two blocks of one mixed cycle
(tameness-free-mutex), \(p\)  has to belong to a mixed cycle \(u_t\) 
other than \(u_i\)  and \(u_j\) . By the maximality of \(j\) , we have \(i<t<j\) . This
implies, however, \(r < r^{\prime }<p<s^{\prime }\) , which contradicts well-nestedness.

Mixed periods
From now on, for each \(i\in [1,k]\) , we use \(e_i\)  to denote the \(i\) -th unit
vector in \(\mathbb {N}^k\) , i.e. the vector with 1 in the \(i\) -th coordinate and 0
otherwise. A mixed period is a vector \(\pi \in \mathbb {N}^k\)  of the form
\(\Vert u_j\Vert \cdot e_i + \Vert u_i\Vert \cdot e_j\) , where \(u_i\)  and \(u_j\)  are mixed cycles.
Let \(\mathbb {P}\subseteq \mathbb {N}^k\)  be the set of
mixed periods. Note that \(|\mathbb {P}|\le k^2\) .
We will need a condition that guarantees that a given period \(\pi \in \mathbb {P}\)  can be
added to a solution \(x\)  to obtain another solution. Suppose we have two blocks
\(p\)  and \(q\)  for which we know that if we insert a string \(f_1\)  to the left
of \(w_p\)  and a string \(f_2\)  to the right of \(w_q\)  and \(f_1f_2\)  cancels to 1
in \(G\) , then the whole word cancels to 1. Which string would we insert to the
left of \(w_p\)  and to the right of \(w_q\)  if we build the solution \(x+\pi \) ?
Suppose \(p\)  is a \(u_i\) -block and \(q\)  is a \(u_j\) -block. Moreover, let \(r\) 
be the first (left-most) \(u_i\) -block and let \(s\)  be the last (right-most)
\(u_j\) -block. If we add \(\Vert u_j\Vert \cdot e_i\)  to \(x\) , this inserts
\(\lambda ^{p-r}(u_i^{\Vert u_j\Vert })\)  to the left of \(w_p\) : Indeed, in the case \(p=r\) ,
we insert \(u_i^{\Vert u_j\Vert }\) ; and when \(p\)  moves one position to the right, the
inserted string is rotated once to the left. Similarly, if we add
\(\Vert u_i\Vert \cdot e_j\)  to \(x\) , we insert \(\rho ^{s-q}(u_j^{\Vert u_i\Vert })\)  to the right of \(w_q\) :
This is clear for \(q=s\)  and decrementing \(q\)  means rotating the inserted string
to the right. This motivates the following definition.
Let \((x,C)\)  be a certified solution and let \(u_i\)  and \(u_j\)  be mixed cycles with \(i<j\) .
Moreover, let \(r \in [1,m]\)  be the left-most \(u_i\) -block and let \(s \in [1,m]\)  be the
right-most \(u_j\) -block. Then the mixed period \(\pi =\Vert u_j\Vert \cdot e_i + \Vert u_i\Vert \cdot e_j\)  is
compatible with \((x,C)\) if there are a \(u_i\) -block \(p\)  and a \(u_j\) -block \(q\) 
such that
\(\lbrace p,q\rbrace \in C \text{ and $\lambda ^{p-r}(u_i^{\Vert u_j\Vert })\rho ^{s-q}(u_j^{\Vert u_i\Vert })$ represents $1$ in $G$} . \) 

With \(\mathbb {P}(x,C)\) , we denote the set of mixed periods that are
compatible with \((x,C)\) . One might wonder why we require an edge \(\lbrace p,q\rbrace \in C\) .
In order to guarantee that \(\lambda ^{p-r}(u_i^{\Vert u_j\Vert })\)  and
\(\rho ^{s-q}(u_j^{\Vert u_i\Vert })\)  can cancel, it would be sufficient to merely forbid
edges \(I\in C\)  that intersect \([p,q]\)  and contain a block outside
of \([p-1,q+1]\) . However, this weaker condition can become false when we insert
other mixed periods. Our stronger condition is preserved, which implies:
Lemma 6.16 
Let \((x,C)\)  be a certified solution. Then every
\(x^{\prime }\in x+\mathbb {P}(x,C)^\oplus \)  is a solution.

It suffices to show that if \((x,C)\)  is a certified solution and
\(\pi \in \mathbb {P}(x,C)\) , then there is a certified solution \((x^{\prime },C^{\prime })\)  such
that \(x^{\prime }=x+\pi \)  and \(\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })\) . Suppose
\(\pi =\Vert u_j\Vert \cdot e_i + \Vert u_i\Vert \cdot e_j \in \mathbb {P}(x,C)\) . Without loss of
generality, assume \(i<j\) . Let \(r\in [1,m]\)  be the left-most
\(u_i\) -block and \(s\in [1,m]\)  be the right-most \(u_j\) -block in \(w\) .
Since \(\pi \in \mathbb {P}(x,C)\) , there is a \(u_i\) -block \(p\)  and a \(u_j\) -block
\(q\)  such that tameness-free-compatibility-cond holds. As
explained above, we can insert \(\lambda ^{p-r}(u_i^{\Vert u_j\Vert })\)  on the left of
\(w_p\)  and \(\rho ^{s-q}(u_j^{\Vert u_i\Vert })\)  on the right of \(w_q\)  and thus obtain a
word \(w^{\prime }\)  that corresponds to the vector \(x^{\prime }=x+\pi \) .
Both inserted words consist of
\(\Vert u_j\Vert \cdot \Vert u_i\Vert \)  many blocks and they cancel to 1, which means we can
construct a cancellation \(C^{\prime }\)  from \(C\)  as follows. Between the two sequences of
inserted blocks, we add two-element edges so that the left-most inserted
\(u_i\) -block is connected to the right-most inserted \(u_j\) -block, and so forth.
The blocks that existed before are connected by edges as in \(C\) . It is clear
that then, \(C^{\prime }\)  is a partition that is consistent, cancelling and maximal. Moreover,
since there is an edge \(\lbrace p,q\rbrace \) , the new edges between the inserted blocks do
not violate well-nestedness: If there were a crossing edge, then there would
have been one that crosses \(\lbrace p,q\rbrace \) .
It remains to verify \(\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })\) .
A mixed period \(\pi ^{\prime } \in \mathbb {P}(x,C) \setminus \lbrace \pi \rbrace \)  is clearly contained
in \(\mathbb {P}(x^{\prime },C^{\prime })\)  too. Hence, it remains to show \(\pi \in \mathbb {P}(x^{\prime },C^{\prime })\) .
This, however, follows from the fact that instead of the edge \(\lbrace p,q\rbrace \)  that witnesses
compatibility of \(\pi \)  with \((x,C)\) , we can use its counterpart in \(C^{\prime }\) ; let us call this edge \(\lbrace p^{\prime },q^{\prime }\rbrace \) :
If \(r^{\prime }\)  is the left-most
\(u_i\) -block in \(w^{\prime }\)  and \(s^{\prime }\)  is the right-most \(u_j\) -block in \(w^{\prime }\) , then \(p^{\prime }-r^{\prime } = p-r + \Vert u_i\Vert  \cdot \Vert u_j\Vert \)  and
\(s^{\prime }-q^{\prime } = s-q + \Vert u_i\Vert  \cdot \Vert u_j\Vert \) . This implies
\(\lambda ^{p-r}(u_i^{\Vert u_j\Vert })=\lambda ^{p^{\prime }-r^{\prime }}(u_i^{\Vert u_j\Vert })\)  and
\(\rho ^{s-q}(u_j^{\Vert u_i\Vert })=\rho ^{s^{\prime }-q^{\prime }}(u_j^{\Vert u_i\Vert })\)  which implies that
tameness-free-compatibility-cond holds for the edge \(\lbrace p^{\prime },q^{\prime }\rbrace \) . This
completes the proof of the tameness-free-periods.
We shall need another auxiliary tameness-free-consecutive.
Lemma 6.17 
Let \(C\)  be a cancellation for \(w\) . Let \(u_i\)  and \(u_j\)  be distinct mixed cycles. Let
\(D\subseteq C\)  be the set of standard edges \(I\in C\)  that contain one block from
\(u_i\)  and one block from \(u_j\) . Then the set
\(B = \lbrace  p \in [1,m] \mid p \text{ is a $u_i$-block}, \exists I \in D : p \in I\rbrace \) 
is an interval.

We prove the case \(i<j\) , the other follows by symmetry. Suppose there are
\(r_1,r_2\in B\)  such that \(r_1<r_2\)  and there is no \(t\in B\)  with \(r_1<t<r_2\) .
Towards a contradiction, suppose \(r_2-r_1>1\) . Since \(r_1,r_2\in B\) , there
are \(I_1,I_2\in D\)  with \(r_1\in I_1\)  and \(r_2\in I_2\) . Let \(I_1=\lbrace r_1,s_1\rbrace \) 
and \(I_2=\lbrace r_2,s_2\rbrace \) . Then \(s_1\)  and \(s_2\)  are \(u_j\) -blocks and by
well-nestedness, we have \(r_1 < r_2 < s_2 < s_1\) . Since \(r_2-r_1>1\) , there is
a \(t\)  with \(r_1<t<r_2\)  and therefore some \(J\in C\)  with \(t\in J\) . Since \(|J|\ge 2\) , there has to be a \(t^{\prime }\in J\) , \(t^{\prime }\ne t\) . However, well-nestedness dictates
that \(t^{\prime }\in [r_1,s_1]\setminus [r_2,s_2]\) . Since \(J\)  cannot contain another
block from \(u_i\)  (tameness-free-mutex), we cannot have \(t^{\prime }\in [r_1,r_2]\) , which only leaves \(t^{\prime }\in [s_2,s_1]\) . Hence, \(t^{\prime }\)  is from
\(u_j\) . By the same argument, any block \(t^{\prime \prime }\in J\setminus \lbrace t,t^{\prime }\rbrace \) 
must be from \(u_i\)  or \(u_j\) , contradicting tameness-free-mutex. This
means \(|J|=2\)  and thus \(t\in B\) , in contradiction to the choice of \(r_1\)  and \(r_2\) .
Let \(M\subseteq [1,k]\)  be the set of \(i\in [1,k]\)  such that \(u_i\)  is a mixed
cycle. We define a new norm on vectors \(x\in \mathbb {N}^k\)  by setting \(\Vert x\Vert _{\mathsf {m}}=\max _{i\in M} x_i\) .
Lemma 6.18 
There is a polynomial \(q\)  such that the following holds. For every certified
solution \((x,C)\)  with \(\Vert x\Vert _{\mathsf {m}}>q(n)\) , there exists a mixed period \(\pi \in \mathbb {P}(x,C)\)  and a certified solution \((x^{\prime },C^{\prime })\)  such that \(x^{\prime }=x-\pi \) 
and \(\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })\) .

We show that the tameness-free-removeperiods holds if \(q(n)\ge (n+3k+1) + kn^2\) . (Recall that \(k\le n\) .) Let \((x,C)\)  be a certified
solution with \(\Vert x\Vert _{\mathsf {m}}>q(n)\) . Then there is a mixed cycle \(u_i\)  such
that \(x_i>q(n)\)  and hence \(u_i^{x_i}\)  consists of more than \(q(n)\)  blocks. Let
\(D\subseteq C\)  be the set of all edges \(I\in C\)  that contain a block
from \(u_i\) . Since an edge can contain at most one block per mixed cycle
(tameness-free-mutex), we have \(|D|>q(n)\) .
Hence, tameness-free-nonstandard tells us
that \(D\)  contains more than \(k n^2\)  standard edges. Hence, there exists a
mixed cycle \(u_j\)  such that the set \(E\subseteq D\)  of standard edges \(I\in D\)  that
consist of one block from \(u_i\)  and one block from \(u_j\) 
satisfies \(|E| > n^2\) . If \(B_i\) 
(resp., \(B_j\) ) denotes the set of blocks from \(u_i\)  (resp., \(u_j\) ) contained in some edge \(I\in E\) , then each of the sets \(B_i\)  and \(B_j\) 
has to be an interval (tameness-free-consecutive) of size more than \(n^2\) .
We only deal with the case \(i<j\) , the case \(i>j\)  can be done similarly.
Let us take a subinterval \([p^{\prime },p]\)  of \(B_i\)  such that \(p-p^{\prime } = \Vert u_i\Vert \cdot \Vert u_j\Vert  \le n^2\) .
By well-nestedness and since \(B_j\)  is an interval, the neighbors (with respect to the edges from \(E\) ) of \([p^{\prime },p]\)  form an interval \([q,q^{\prime }] \subseteq B_j\) 
as well, and we have \(p-p^{\prime }=q^{\prime }-q=\Vert u_i\Vert \cdot \Vert u_j\Vert \) .
Moreover, we have an edge \(\lbrace p-\ell , q+\ell \rbrace  \in E\)  for each
\(\ell \in [0,p-p^{\prime }]\) . In particular, \(w_{p^{\prime }}w_{p^{\prime }+1}\cdots w_{p-1}w_{q+1}\cdots w_{q^{\prime }}\)  represents 1 in \(G\) .
Let \(r\)  be the left-most \(u_i\) -block and let \(s\)  be the right-most
\(u_j\) -block. Then, as shown before the definition of compatibility
(p. REF ), we have
\(\lambda ^{p-r}(u_i^{\Vert u_j\Vert }) = w_{p^{\prime }}w_{p^{\prime }+1}\cdots w_{p-1}, && \rho ^{s-q}(u_j^{\Vert u_i\Vert }) = w_{q+1}w_{q+1}\cdots w_{q^{\prime }}.\) 

Therefore,
\(\lambda ^{p-r}(u_i^{\Vert u_j\Vert })\rho ^{s-q}(u_j^{\Vert u_i\Vert })\) 
represents 1 in \(G\)  and \(\lbrace p,q\rbrace \)  witnesses compatibility of
\(\pi =\Vert u_j\Vert \cdot e_i+\Vert u_i\Vert \cdot e_j\)  with \((x,C)\) . Hence,
\(\pi \in \mathbb {P}(x,C)\) .
Let \(x^{\prime }=x-\pi \) . We remove the factors \(w_{p^{\prime }} \cdots w_{p-1}\)  and
\(w_{q+1}\cdots w_{q^{\prime }}\)  from \(w\) . Then, the remaining blocks spell
\(w^{\prime }=v_0u_1^{x^{\prime }_1}v_1\cdots u_k^{x^{\prime }_k}v_k\) .
Indeed, recall that removing from a word \(y^t\)  any factor of length \(\ell \cdot |y|\)  will result in the word \(y^{t-\ell }\) . Moreover, let \(C^{\prime }\)  be the set of
edges that agree with \(C\)  on the remaining blocks. By the choice of the
removed blocks, it is clear that \(C^{\prime }\)  is a cancellation for \(w^{\prime }\) . Hence,
\((x^{\prime },C^{\prime })\)  is a certified solution.
It remains to verify \(\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })\) .
First note that for every mixed cycle \(u_\ell \) , all
\(u_\ell \) -blocks that remain in \(w^{\prime }\)  change their position relative to the left-most and the
right-most \(u_\ell \) -block by a difference that is divisible by \(\Vert u_\ell \Vert \)  (if \(i \ne \ell \ne j\) 
then these relative positions do not change at all).
Note that the expression \(\lambda ^{p-r}(u_i^{\Vert u_j\Vert })\)  is not altered when
\(p-r\)  changes by a difference divisible by \(\Vert u_i\Vert \) , and an analogous
fact holds for \(\rho ^{s-q}(u_j^{\Vert u_i\Vert })\) .
Hence, the edge in \(C^{\prime }\)  that corresponds
to the \(C\) -edge \(\lbrace p,q\rbrace \)  is a witness for \(\pi \in \mathbb {P}(x^{\prime },C^{\prime })\) .
Moreover, for all other mixed periods \(\pi ^{\prime } \in \mathbb {P}(x,C) \setminus \lbrace \pi \rbrace \)  that are witnessed
by an edge \(\lbrace t,u\rbrace  \in C\) , the blocks \(t\)  and \(u\)  do not belong to \([p^{\prime },p-1] \cup [q+1,q^{\prime }]\) .
Therefore, the corresponding edge in \(C^{\prime }\)  exists and serves as a witness for
\(\pi ^{\prime } \in \mathbb {P}(x^{\prime },C^{\prime })\) .
Repeated application of tameness-free-periods now yields:
Lemma 6.19 
There exists a polynomial \(q\)  such that the following holds.
For every solution \(x\in \mathbb {N}^k\) , there exists a certified solution
\((x^{\prime },C^{\prime })\)  such that \(\Vert x^{\prime }\Vert _{\mathsf {m}} \le q(n)\)  and \(x\in x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })^\oplus \) .

Let \(q\)  be the polynomial provided by tameness-free-removeperiods.
Since \(x\)  is a solution, there is a certified solution \((x,C)\) . Repeated
application of tameness-free-removeperiods yields certified solutions
\((x_0,C_0),\ldots ,(x_m,C_m)\)  and mixed periods \(\pi _1,\ldots ,\pi _m\)  such that
\((x_0,C_0)=(x,C)\) , \(\pi _i\in \mathbb {P}(x_{i-1},C_{i-1}) \subseteq \mathbb {P}(x_i,C_i)\) ,
\(x_{i}=x_{i-1}-\pi _i\) , and \(\Vert x_m\Vert _{\mathsf {m}} \le q(n)\) . In
particular, \(\mathbb {P}(x_m,C_m)\)  contains each \(\pi _i\)  and hence
\(x=x_m+\pi _1+\cdots +\pi _m\in x_m+\mathbb {P}(x_m,C_m)^\oplus . \) 
Thus, \((x^{\prime },C^{\prime })=(x_m,C_m)\)  is the desired certified solution.
We are now ready to prove tameness-free-preserved and thus tforest-tame.
Suppose that \(p_0\)  and \(p_1\)  are the polynomials guaranteed by the knapsack
tameness of \(G_0\)  and \(G_1\) , respectively. Recall that \(S\subseteq \mathbb {N}^k\)  is the
set of solutions to tameness-free-expeq. We prove that there exists a
polynomial \(p\)  such that for every \(x \in S\) 
there is a semilinear set \(S^{\prime }\subseteq \mathbb {N}^k\)  of
magnitude at most \(p(n)\)  such that \(x\in S^{\prime }\subseteq S\) . This clearly implies
that \(S\)  has magnitude at most \(p(n)\) .
First, we apply tameness-free-mixed. It yields a polynomial \(q\)  and a
certified solution \((x^{\prime },C^{\prime })\)  with \(\Vert x^{\prime }\Vert _{\mathsf {m}}\le q(n)\)  such that \(x\in x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })^\oplus \) . Let
\(w^{\prime } = v_0u_1^{x^{\prime }_1}v_1\cdots u_k^{x^{\prime }_k}v_k\) 
and consider \(w^{\prime }\)  decomposed into blocks as we did above with \(w\) .
Let \(T\subseteq [1,k]\)  be the set of all \(i\in [1,k]\)  for which the cycle
\(u_i\)  is simple. Since \(C^{\prime }\)  is maximal, for each \(i\in T\) , all \(u_i\) -blocks
are contained in one edge \(I_i\in C^{\prime }\) . Note that it is allowed that one edge
contains the blocks of multiple simple cycles. We partition \( T\)  into
sets \( T= T_1\uplus \cdots \uplus T_t\)  so that \(i\in T\)  and
\(j\in T\)  belong to the same part if and only if the \(u_i\) -blocks and the
\(u_j\) -blocks belong to the same edge of \(C\) , i.e. \(I_i=I_j\) .
For a moment, let us fix an \(\ell \in [1,t]\)  and let \(I\in C^{\prime }\)  be the edge
containing all \(u_i\) -blocks for all the \(i\in T_\ell \) . Moreover, let
\( T_\ell =\lbrace i_1,\ldots ,i_r\rbrace \) . The words \(\bar{v}_j\)  for \(j\in [0,r]\)  will
collect those blocks that belong to \(I\)  but are not \(u_{i_s}\) -blocks for any
\(s\in [1,r]\) . Formally, \(\bar{v}_0\)  consists of all blocks that belong to \(I\) 
that are to the left of all \(u_{i_1}\) -blocks. Similarly, \(\bar{v}_r\)  is the
concatenation of all blocks belonging to \(I\)  that are to the right of all
\(u_{i_r}\) -blocks. Finally, for \(j\in [1,r-1]\) , \(\bar{v}_j\)  consists of all
blocks that belong to \(I\)  and are to the right of all \(u_{i_j}\) -blocks and to
the left of all \(u_{i_{j+1}}\) -blocks.
By consistency of \(C^{\prime }\) , for some \(s\in \lbrace 0,1\rbrace \) , all the words \(\bar{v}_j\)  for
\(j\in [0,r]\)  and the words \(u_{i_j}\)  for \(j\in [1,r]\)  belong to \(A_s^*\)  and thus
represent elements of \(G_s\) . Since \(G_s\)  is knapsack tame, we know that the set
\( S_\ell =\lbrace  z\in \mathbb {N}^k \mid \bar{v}_0 u_{i_1}^{z_{i_1}} \bar{v}_1 u_{i_2}^{z_{i_2}} \bar{v}_2\cdots u_{i_r}^{z_{i_r}}\bar{v}_r~\text{represents $1$ in $G_s$,~~ $z_j=0$ for $j\notin T_\ell $}\rbrace \) 
has magnitude at most \(p_s(n)\) . Consider the
vector \(y\in \mathbb {N}^k\)  with \(y_i=0\)  for \(i\in T\)  and \(y_i=x^{\prime }_i\)  for \(i\in [1,k]\setminus T\)  (i.e. when \(u_i\)  is a mixed cycle). We claim that
\(S^{\prime } = y + S_1 + \cdots S_t + \mathbb {P}(x^{\prime },C^{\prime })^\oplus \) 
has magnitude at most \(q(n)+p_0(n)+p_1(n)+n\)  and satisfies \(x\in S^{\prime }\subseteq S\) .
First, since \(y\)  and the members of \(S_1,\ldots ,S_t\)  are non-zero on pairwise
disjoint coordinates, the magnitude of \(y+S_1+\cdots +S_t\)  is the maximum of
\(\Vert y\Vert \)  and the maximal magnitude of \(S_1,\ldots ,S_\ell \) . Hence, it is
bounded by \(q(n)+p_0(n)+p_1(n)\) . The summand \(\mathbb {P}(x^{\prime },C^{\prime })^\oplus \)  contributes
only periods, and their magnitude is bounded by \(n\)  (recall that they are mixed
periods). Thus, the magnitude of \(S^{\prime }\)  is at most \(p(n)=q(n)+p_0(n)+p_1(n)+n\) .
The cancelling property of \((x^{\prime },C^{\prime })\)  tells us that \(x^{\prime }-y\)  is contained in
\(S_1+\cdots +S_t\) . By the choice of \((x^{\prime },C^{\prime })\) , we have \(x\in x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })^\oplus \) . Together, this means \(x\in S^{\prime }\) . Hence, it
remains to show \(S^{\prime }\subseteq S\) . To this end, consider a vector \(x^{\prime \prime }\in y+S_1+\cdots +S_t\) . It differs from \(x^{\prime }\)  only in the exponents at simple
cycles. Therefore, we can apply essentially the same cancellation to \(x^{\prime \prime }\)  as
to \(x^{\prime }\) : we just need to adjust the edges containing the blocks of simple
cycles. It is therefore clear that the resulting cancellation \(C^{\prime \prime }\)  has the
same compatible mixed periods as \(C^{\prime }\) : \(\mathbb {P}(x^{\prime \prime },C^{\prime \prime })=\mathbb {P}(x^{\prime },C^{\prime })\) .
Thus, by tameness-free-periods, we have \(x^{\prime \prime }+\mathbb {P}(x^{\prime },C^{\prime })^\oplus \subseteq S\) . This proves \(S^{\prime } = y+S_1+\cdots +S_t+\mathbb {P}(x^{\prime },C^{\prime })^\oplus \subseteq S\)  and hence the tameness-free-preserved.

\(\mathsf {LogCFL}\) -membership
In this section, we prove the upper bound in logcfl-completeness:
Proposition 6.20 
Let \(G=\mathbb {G}(A,I)\)  be a graph group where \((A,I)\)  is a transitive forest. Then
the knapsack problem and the subset sum problem for \(G\)  belong to \(\mathsf {LogCFL}\) .

Let us consider knapsack.
According to thm-acyclic-logcfl, it suffices to provide a logspace reduction from the
knapsack problem over \(G\)  to the membership problem for acyclic automata over
\(G\) . Suppose we have an instance \(h_0g_1^{\mathsf {x}_1}h_1\cdots g_k^{\mathsf {x}_k} h_k=1\)  of
the knapsack problem over \(G\)  of size \(n\) . Moreover, let \(h_i\)  be represented
by \(v_i\in A^*\)  for each \(i\in [0,k]\)  and let \(g_i\)  be represented by \(u_i\in A^*\)  for \(i\in [1,k]\) .
By tforest-tame, there is a polynomial \(p\)  such that the
above instance has a solution if and only if it has a solution \(x\in \mathbb {N}^k\)  with
\(\Vert x\Vert  \le p(n)\) . We construct an acyclic automaton
\(\mathcal {A}=(Q,A,\Delta ,q_0,q_f)\)  as follows. It has the state set \(Q=[0,k+1]\times [0,p(n)]\)  and the following transitions. From \((0,0)\) , there is one transition
labeled \(v_0\)  to \((1,0)\) . For each \(i\in [1,k]\)  and \(j\in [0,p(n)-1]\) , there are
two transitions from \((i,j)\)  to \((i,j+1)\) ; one labeled by \(u_i\)  and one labeled
by \(\varepsilon \) . Furthermore, there is a transition from \((i,p(n))\)  to
\((i+1,0)\)  labeled \(v_i\)  for each \(i\in [1,k]\) . The initial state is \(q_0=(0,0)\) 
and the final state is \(q_f=(k+1,0)\) .
It is clear that \(\mathcal {A}\)  accepts a word that represents 1 if and only if the
exponent equation has a solution. Finally, the reduction can clearly be
carried out in logarithmic space.
For subset sum the same reduction as above works but the polynomial bound on solutions is for free.

\(\mathsf {LogCFL}\) -hardness
It remains to show the lower bound
in logcfl-completeness. If \((A,I)\)  is not complete, then \((A,I)\)  contains two
non-adjacent vertices and thus \(\mathbb {G}(A,I)\)  contains an isomorphic copy of \(F_2\) ,
the free group of rank two. Hence, we will show that knapsack and subset sum for \(F_2\)  are
\(\mathsf {LogCFL}\) -hard. Let \(\lbrace a,b\rbrace \)  be a generating set for \(F_2\) . Let \(\theta \colon \lbrace a,b,a^{-1},b^{-1}\rbrace ^* \rightarrow F_2\)  be the morphism that maps a word \(w\)  to
the group element represented by \(w\) .
A valence automaton over a group
\(G\)  is a tuple \(\mathcal {A}=(Q,\Sigma ,\Delta ,q_0,q_f)\)  where \(Q\) , \(\Sigma \) , \(q_0\) , \(q_f\) 
are as in a finite automaton and \(\Delta \)  is a finite subset of
\(Q\times \Sigma ^*\times G\times Q\) . The language accepted by \(\mathcal {A}\) is denoted \(L(\mathcal {A})\)  and consists of
all words \(w_1\cdots w_n\)  such that there is a computation
\(p_0\xrightarrow{} p_1 \rightarrow \cdots \rightarrow p_{n-1}\xrightarrow{} p_n\) 
such that \((p_{i-1}, w_i, g_i, p_i)\in \Delta \)  for \(i\in [1,n]\) , \(p_0=q_0\) , \(p_n=q_f\) , and \(g_1\cdots g_n=1\)  in \(G\) .
We call this computation also an accepting run of \(\mathcal {A}\)  for \(w\)  (of length \(n\) ). Note that we allow \(\varepsilon \) -transitions of the form
\((p,\varepsilon ,g,q) \in \Delta \) . This implies that an accepting run for a word \(w\)  can be of length
greater than \(|w|\) .
An analysis of a proof (in this case [9]}) of the Chomsky-Schützenberger theorem yields:
Lemma 6.21 
For every language \(L \subseteq \Sigma ^*\) 
the following statements are equivalent:

\(L\)  is context-free.

There is a valence automaton \(\mathcal {A}\)  over \(F_2\)  such that \(L = L(\mathcal {A})\) .

There is a valence automaton \(\mathcal {A}\)  over \(F_2\)  and a constant \(c \in \mathbb {N}\)  such that \(L = L(\mathcal {A})\)  and
for every \(w \in L\)  there exists an accepting run of \(\mathcal {A}\)  for \(w\)  of length at most \(c \cdot |w|\) .


<FIGURE>The equivalence of (i) and (ii) is well known (see [9]}) and the implication from (iii) to (ii) is trivial.
We show that (i) implies (iii). For this,
we shall use the concept of rational transductions. If \(\Sigma \)  and \(\Gamma \) 
are alphabets, subsets \(T\subseteq \Gamma ^*\times \Sigma ^*\)  are called
transductions. Given a language \(L\subseteq \Sigma ^*\)  and a transduction
\(T\subseteq \Gamma ^*\times \Sigma ^*\) , we define
\( TL=\lbrace u\in \Gamma ^* \mid \text{$(u,v)\in T$ for some $v\in L$} \rbrace . \) 
A finite-state transducer is a tuple
\(\mathcal {A}=(Q,\Sigma ,\Gamma ,\Delta ,q_0,q_f)\) , where \(Q\)  is a finite set of
states, \(\Sigma \)  is its input alphabet, \(\Gamma \)  is its
output alphabet, \(\Delta \)  is a finite subset of
\(Q\times \Gamma ^*\times \Sigma ^*\times Q\) , \(q_0\in Q\)  is its initial
state, and \(q_f\in Q\)  is its final state. The elements of \(\Delta \)  are
called transitions. We say that a pair \((u,v)\in \Gamma ^*\times \Sigma ^*\) 
is accepted by \(\mathcal {A}\) if there is a sequence
\((p_0,u_1,v_1,p_1),(p_1,u_2,v_2,p_2),\ldots ,(p_{n-1},u_n,v_n,p_n)\)  of
transitions where \(n\ge 1\) , \(p_0=q_0\) , \(p_n=q_f\) , \(u=u_1\cdots u_n\) , and
\(v=v_1\cdots v_n\) . The set of all pairs \((u,v)\in \Gamma ^*\times \Sigma ^*\)  that
are accepted by \(\mathcal {A}\)  is denoted by \(T(\mathcal {A})\) . A transduction \(T\subseteq \Gamma ^*\times \Sigma ^*\)  is called rational if there is a finite-state
transducer \(\mathcal {A}\)  with \(T(\mathcal {A})=T\) .
Let \(W_2\subseteq \lbrace a,b,a^{-1},b^{-1}\rbrace ^*\)  be the word problem of \(F_2\) , i.e.
\( W_2=\lbrace w\in \lbrace a,b,a^{-1},b^{-1}\rbrace ^* \mid \theta (w)=1\rbrace . \) 
For languages \(K\subseteq \Gamma ^*\)  and \(L\subseteq \Sigma ^*\) , we write
\(K\leadsto L\)  if there is a rational transduction \(T \subseteq \Gamma ^* \times \Sigma ^*\)  and a constant \(c\)  such
that \(K=TL\)  and for each \(u\in K\) , there is a \(v\in L\)  with \(|v|\le c|u|\)  and
\((u,v)\in T\) . Observe that the relation \(\leadsto \)  is transitive, meaning that it suffices
to show \(L\leadsto W_2\)  for every context-free language \(L\) .
Let \(D_2\)  be the one-sided Dyck language over two pairs of parentheses, in
other words: \(D_2\)  is the smallest language \(D_2\subseteq \lbrace x,\bar{x},y,\bar{y}\rbrace ^*\)  such that \(\varepsilon \in D_2\)  and whenever \(uv\in D_2\) , we also have \(uwv\in D_2\)  for \(w\in \lbrace x\bar{x}, y\bar{y}\rbrace \) .
It is easy to see that \(L\leadsto D_2\)  for every context-free language \(L\) .
Indeed, an \(\varepsilon \) -free pushdown automaton (which exists for every
context-free language [11]}) for \(L\)  can be converted into a transducer
witnessing \(L\leadsto D_2\) . Therefore, it remains to show that \(D_2\leadsto W_2\) .
Let \(F_3\)  be the free group of rank 3 and let \(\lbrace a,b,\#\rbrace \)  be a free
generating set for \(F_3\) . As above, let
\( W_3=\lbrace w\in \lbrace a,b,\#,a^{-1},b^{-1},\#^{-1}\rbrace ^* \mid \text{$w$ represents $1$ in $F_3$}\rbrace  \) 
be the word problem of \(F_3\) . Since \(F_3\)  can be embedded into
\(F_2\)  [12]}, we clearly have \(W_3\leadsto W_2\) . It therefore suffices to
show \(D_2\leadsto W_3\) .
For this, we use a construction of Kambites [9]}. He proves
that if \(\mathcal {A}\)  is the transducer in transducer-kambites and \(T=T(\mathcal {A})\) ,
then \(D_2=TW_3\) . Thus, for every \(u\in D_2\) , we have \((u,v)\in T\)  for some
\(v\in W_3\) . An inspection of \(\mathcal {A}\)  yields that \(|v|=2|u|+|v|_{\#^{-1}}\)  and
\(|v|_{\#}=|u|\) . Since \(v\in W_3\) , we have \(|v|_{\#^{-1}}=|v|_{\#}\)  and thus
\(|v|=3|u|\) . Hence, the transduction \(T\)  witnesses \(D_2\leadsto W_3\) . We have
thus shown \(L\leadsto D_2\leadsto W_3\leadsto W_2\)  and hence the
lemma-kambites.
Given \(w\) , it is easy to convert the valence automaton \(\mathcal {A}\)  from
lemma-kambites into an acyclic automaton that exhausts all computations
of \(\mathcal {A}\)  of length \(c\cdot |w|\) . This yields the following.
Proposition 6.22 
For \(F_2\) , the membership problem for acyclic automata is \(\mathsf {LogCFL}\) -hard.

Fix a context-free language \(L \subseteq \Sigma ^*\)  with a
\(\mathsf {LogCFL}\) -complete membership problem; such languages exist [14]}.
Fix a valence automaton \(\mathcal {A}=(Q,\Sigma ,\Delta ,q_0,q_f)\)  over \(F_2\)  and a constant \(c \in \mathbb {N}\)  such that the statement
of lemma-kambites(iii) holds for \(L\) , \(\mathcal {A}\) , and \(c\) .
Consider a word \(w \in \Sigma ^*\) . From \(w\)  we construct an acyclic automaton \(\mathcal {B}\)  over
the input alphabet \(\lbrace a,b,a^{-1},b^{-1}\rbrace \)  such that \(1 \in \theta (L(\mathcal {B}))\)  if and only if \(w \in L\) .
Let \(m = |w|\) , \(w = a_1 a_2 \cdots a_m\)  and \(n = c \cdot m\) .
The set of states of \(\mathcal {B}\)  is \([0,m] \times [0,n] \times Q\) .
The transitions of \(\mathcal {B}\)  are defined as follows:

\((i-1,j-1,p) \xrightarrow{} (i,j,q)\)  if \((p,a_i, x, q) \in \Delta \)  for all \(i \in [1,m]\) , \(j \in [1,n]\) , and \(x \in \lbrace a,b,a^{-1},b^{-1}\rbrace ^*\)

\((i,j-1,p) \xrightarrow{} (i,j,q)\)  if \((p,\varepsilon , x, q) \in \Delta \)  for all \(i \in [0,m]\) , \(j \in [1,n]\) , and \(x \in \lbrace a,b,a^{-1},b^{-1}\rbrace ^*\)

The initial state of \(\mathcal {B}\)  is \((0,0,q_0)\)  and all states
\((m,j,q_f)\)  with \(j \in [0,n]\)  are final in \(\mathcal {B}\) . It is then straightforward to show that
\(1 \in \theta (L(\mathcal {B}))\)  if and only if \(w \in L\) . The intuitive idea is that in a state of \(\mathcal {B}\)  we store in the first component
the current position in the word \(w\) . In this way we enforce the simulation of a run of \(\mathcal {A}\)  on input \(w\) . In the second
component of the state we store the total number of simulated \(\mathcal {A}\) -transitions. In this way we make \(\mathcal {B}\)  acyclic.
Finally, the third state component of \(\mathcal {B}\)  stores the current \(\mathcal {A}\) -state.
Proposition 6.23 For \(F_2\) , knapsack and subset sum are \(\mathsf {LogCFL}\) -hard.

Let \(\mathcal {A} = (Q,\lbrace a,b,a^{-1},b^{-1}\rbrace , \Delta , q_0, q_f)\)  be an acyclic automaton. We construct words \(w, w_1, \ldots , w_m \in \lbrace a,b,a^{-1},b^{-1}\rbrace \) 
such that the following three statements are equivalent:

\(1 \in \theta (L(\mathcal {A})\) .

\(\theta (w) \in \theta (w_1^* w_2^* \cdots w_m^*)\) .

\(\theta (w) \in \theta (w_1^{e_1} w_2^{e_2} \cdots w_m^{e_m})\)  for some \(e_1, e_2, \ldots , e_m \in \lbrace 0,1\rbrace \) .

W.l.o.g. assume that \(Q = \lbrace 1,\ldots , n\rbrace \) , where 1 is the initial state and \(n\)  is the unique final state of \(\mathcal {A}\) .
Let \(\alpha _i = a^i b a^{-i}\)  for \(i\in [1,n+2]\) . It is well known that
the \(\alpha _i\)  generate a free subgroup of rank \(n+2\)  in \(F_2\)  [12]}. Define the embedding \(\varphi \colon F_2 \rightarrow F_2\) 
by \(\varphi (a) = \alpha _{n+1}\)  and \(\varphi (b) = \alpha _{n+2}\) . For a transition
\(t = (p,w,q) \in \Delta \)  let \(\tilde{t} = \alpha _p \varphi (w) \alpha _q^{-1}\) . Let \(\Delta =\lbrace t_1, \ldots , t_m\rbrace \)  such that
\(t_i = (p,a,q)\)  and \(t_j = (q,b,r)\)  implies \(i < j\) . Since \(\mathcal {A}\)  is acyclic, such an enumeration must exist.
Together with the fact that the \(\alpha _i\)  generate a free group, it follows that the following three statements are equivalent:

\(1 \in \theta (L(\mathcal {A})\) .

\(\theta (\alpha _1 \alpha _n^{-1}) \in \theta (\tilde{t}_1^* \, \tilde{t}_2^* \cdots \tilde{t}_m^*)\) .

\(\theta (\alpha _1 \alpha _n^{-1}) \in \theta (\tilde{t}_1^{e_1} \,\tilde{t}_2^{e_2} \cdots \tilde{t}_m^{e_m})\)  for some \(e_1, e_2, \ldots , e_m \in \lbrace 0,1\rbrace \) .

This shows the proposition.

\(\mathsf {NP}\) -completeness
In [6]}, the authors proved that knapsack for the graph group \(\mathbb {G}(\mathsf {C4}) \cong F_2 \times F_2\)  is NP-complete.
Here we extend this result to all graph groups \(\mathbb {G}(A,I)\)  where \((A,I)\)  is not a transitive forest. For this, it suffices to show that
knapsack for \(\mathbb {G}(\mathsf {P4})\)  is NP-complete. We take the copy \((\lbrace a,b,c,d\rbrace , I)\)  of \(\mathsf {P4}\)  shown in Figure REF .
An acyclic loop automaton is a finite automaton \(\mathcal {A} =(Q,\Sigma , \Delta , q_0, q_f)\)  such that there exists a linear order \(\preceq \) 
on \(\Delta \)  having the property that for all \((p,u,q), (q,v,r) \in \Delta \)  it
holds \((p,u,q) \preceq (q,v,r)\) . Thus, an acyclic loop automaton is obtained
from an acyclic automaton by attaching to some of the states a unique loop.
For a trace monoid \(\mathbb {M}(A,I)\) , the intersection nonemptiness problem for acyclic loop automata
is the following computational problem:
Input: Two acyclic loop automata \(\mathcal {A}_1\) , \(\mathcal {A}_2\)  over the input alphabet \(A\) .
Question: Does \([L(\mathcal {A}_1)]_I \cap [L(\mathcal {A}_2)]_I \ne \emptyset \)  hold?
Aalbersberg and Hoogeboom [17]} proved that for the trace monoid
\(\mathbb {M}(\mathsf {P4})\)  the intersection nonemptiness problem for arbitrary finite
automata is undecidable. We use their technique to show:
Lemma 7.1 
For \(\mathbb {M}(\mathsf {P4})\) , intersection nonemptiness for acyclic loop automata
is NP-hard.

We give a reduction from 3SAT. Let \(\varphi = \bigwedge _{i=1}^m C_i\)  where for every \(i\in [1,m]\) ,
\(C_i = (L_{i,1} \vee L_{i,2} \vee L_{i,3})\)  is a clause consisting of three literals. Let \(x_1, \ldots , x_n\)  be
the boolean variables that occur in \(\varphi \) . In particular, every literal \(L_{i,j}\)  belongs to the set \(\lbrace x_1, \ldots , x_n, \lnot x_1, \ldots , \lnot x_n \rbrace \) .
Let \(p_1, p_2, \ldots , p_n\)  be a list of the first \(n\)  prime numbers. So, for each boolean variable \(x_i\)  we have the
corresponding prime number \(p_i\) . We encode a valuation \(\beta \colon \lbrace x_1, \ldots , x_n \rbrace  \rightarrow \lbrace 0,1\rbrace \)  by any natural number
\(N\)  such that \(N \equiv 0 \bmod p_i\)  if and only if \(\beta (x_i) = 1\) .
For a positive literal \(x_i\)  let \(S(x_i) = \lbrace  p_i \cdot n \mid n \in \mathbb {N}\rbrace \)  and for a negative
literal \(\lnot x_i\)  let \(S(\lnot x_i) = \lbrace  p_i \cdot n + r \mid n \in \mathbb {N}, r\in [1,p_i-1]\rbrace \) .
Moreover, for every \(i\in [1,m]\)  let
\(S_i = S(L_{i,1}) \cup S(L_{i,2}) \cup S(L_{i,3}) .\) 
Thus, \(S_i\)  is the set of all numbers that encode a valuation, which makes the clause \(C_i\)  true.
Hence, the set
\(S = \bigcap _{i=1}^n S_i\) 
encodes the set of all valuations that make \(\varphi \)  true.
We first construct an acyclic loop automaton \(\mathcal {A}_1\)  with
\(L(\mathcal {A}_1) = \prod _{i=1}^m \lbrace  a (bc)^{N_i} d \mid N_i \in S_i \rbrace  .\) 
Note that \(\varphi \)  is satisfiable iff \([L(\mathcal {A}_1)]_I\)  contains a trace from \([\lbrace  (a (bc)^N d)^m \mid N \in \mathbb {N}\rbrace ]_I\) .
We will ensure this property with a second acyclic loop automaton \(\mathcal {A}_2\)  that satisfies the equality
\(L(\mathcal {A}_2) = b^* (ad (bc)^*)^{m-1} ad c^* .\)
We claim that \([L(\mathcal {A}_1)]_I \cap [L(\mathcal {A}_2)]_I = [\lbrace  (a (bc)^N d)^m \mid N \in S\rbrace ]_I\) .
First assume that \(w \equiv _I (a (bc)^N d)^m\)  for some \(N \in S\) .
We have
\(w \equiv _I (a (bc)^N d)^m \equiv _I b^N (ad (bc)^N)^{m-1} ad c^N\) 
and thus \([w]_I \in [L(\mathcal {A}_2)]_I\) .
Moreover, since \(N \in S\)  we get \([w]_I \in [L(\mathcal {A}_1)]_I\) .
For the other direction, let \([w]_I \in [L(\mathcal {A}_1)]_I \cap [L(\mathcal {A}_2)]_I\) .
Thus
\(w \equiv _I \prod _{i=1}^m (a (bc)^{N_i} d) \equiv b^{N_1} \bigg ( \prod _{i=1}^{m-1} (ad c^{N_i} b^{N_{i+1}}) \bigg ) ad c^{N_m} ,\) 
where \(N_i \in S_i\)  for \(i\in [1,m]\) . Moreover, the fact that \([w]_I \in [L(\mathcal {A}_2)]_I\) 
means hat there are \(k_0, k_1, \ldots , k_{m-1}, k_m \ge 0\)  with
\(b^{N_1} \bigg ( \prod _{i=1}^{m-1} (ad c^{N_i} b^{N_{i+1}}) \bigg ) ad c^{N_m} & \equiv _Ib^{k_0} \bigg ( \prod _{i=1}^{m-1} (ad (bc)^{k_i}) \bigg ) ad c^{k_m} \\&\equiv _I b^{k_0} \bigg ( \prod _{i=1}^{m-1} (ad b^{k_i} c^{k_i}) \bigg ) ad c^{k_m} .\) 

Since every symbol is dependent from \(a\)  or \(d\) , this identity implies \(N_i = N_{i+1}\)  for \(i\in [1,m-1]\) .
Thus, \([w]_I \in [\lbrace  (a (bc)^N d)^m \mid N \in S\rbrace ]_I\) .
For a graph group \(\mathbb {G}(A,I)\)  the membership problem for acyclic loop automata
is the following computational problem:
Input: An acyclic loop automaton \(\mathcal {A}\)  over the input alphabet \(A \cup A^{-1}\) .
Question: Is there a word \(w \in L(\mathcal {A})\)  such that \(w=1\)  in \(\mathbb {G}(A,I)\) ?
It is straightforward to reduce the intersection nonemptiness problem for acyclic loop automata over \(\mathbb {M}(A,I)\) 
to the membership problem for acyclic loop automata over \(\mathbb {G}(A,I)\) .
For the rest of this section let \(\Sigma = \lbrace a,b,c,d,a^{-1},b^{-1},c^{-1},d^{-1}\rbrace \)  and
let \(\theta \colon \Sigma ^* \rightarrow \mathbb {G}(P_4)\)  be the canonical homomorphism that maps a word over \(\Sigma \) 
to the corresponding group element.
Lemma 7.2 
For \(\mathbb {G}(\mathsf {P4})\) , the membership problem for acyclic loop automata
is NP-hard.

The lemma follows easily from Lemma REF .
Note that \([L(\mathcal {A}_1)]_I \cap [L(\mathcal {A}_2)]_I \ne \emptyset \)  if and only if \(1 \in \theta (L(\mathcal {A}_1) L(\mathcal {A}_2)^{-1})\)  in the
graph group \(\mathbb {G}(\mathsf {P4})\) .
Moreover, it is straightforward to construct from acyclic loop automata \(\mathcal {A}_1\)  and \(\mathcal {A}_2\)  an acyclic loop automaton for
\(L(\mathcal {A}_1) L(\mathcal {A}_2)^{-1}\) . We only have to replace every transition label \(w\)  in \(\mathcal {A}_2\)  by \(w^{-1}\) , then reverse all transitions in \(\mathcal {A}_2\) 
and concatenate the resulting automaton with \(\mathcal {A}_1\)  on the left.
We can now use a construction from [5]} to reduce knapsack to membership for acyclic loop automata.
Lemma 7.3 
Knapsack for the graph group \(\mathbb {G}(\mathsf {P4})\)  is NP-hard.

By Lemma REF  it suffices to reduce for \(\mathbb {G}(\mathsf {P4})\) 
the membership problem for acyclic loop automata to knapsack.
Let \(\mathcal {A} = (Q, \Sigma ,\Delta , q_0, q_f)\)  be an acyclic loop automaton with transitions
\(\Delta \subseteq Q \times \Sigma ^* \times Q\) . W.l.o.g. assume that \(Q = \lbrace 1, \ldots , n\rbrace \) .
We reuse a construction from [5]},
where the rational subset membership problem for \(\mathbb {G}(\mathsf {P4})\)  was reduced to the submonoid
membership problem for \(\mathbb {G}(\mathsf {P4})\) .
For a state \(q \in Q\)  let \(\widetilde{q} = (ada)^q d (ada)^{-q} \in \Sigma ^*\) .
Let us fix the morphism \(\varphi \colon \Sigma ^* \rightarrow \Sigma ^*\)  with \(\varphi (x) = xx\)  for \(x \in \Sigma \) .
For a transition
\(t = (p,w,q) \in \Delta \)  let \(\tilde{t} = \widetilde{p} \,\varphi (w)\, \widetilde{q}^{-1}\)  and define
\(S=\lbrace  \tilde{t} \mid t \in \Delta \rbrace ^*\) .
In [5]} it was shown that \(1 \in \theta (L(A))\)  if and only if \(\theta (\widetilde{q_0} \, \widetilde{q_f}^{-1}) \in \theta (S)\) .
We construct in polynomial time a knapsack instance over \(\mathbb {G}(P_4)\)  from the automaton \(\mathcal {A}\)  as follows:
Let us choose an enumeration \(t_1, t_2, \ldots , t_m\)  of the transitions of \(\mathcal {A}\)  such that the following holds,
where \(t_i = (p_i, w_i, q_i)\) : If \(q_j = p_k\)  then \(j \le k\) . Since \(\mathcal {A}\) 
is an acyclic loop automaton such an enumeration exists.
The following claim proves the theorem.
Claim: \(1 \in \theta (L(\mathcal {A}))\)  if and only if \(\theta (\widetilde{q_0}\, \widetilde{q_f}^{-1}) \in \theta ( \tilde{t}_1^*\, \tilde{t}_2^* \cdots \tilde{t}_m^*)\) .
One direction is clear: If \(\theta (\widetilde{q_0}\, \widetilde{q_f}^{-1}) \in \theta ( \tilde{t}_1^*\, \tilde{t}_2^* \cdots \tilde{t}_m^*)\) , then
\(\theta (\widetilde{q_0} \,\widetilde{q_f}^{-1}) \in \theta (S)\) . Hence, by [5]} we have \(1 \in \theta (L(\mathcal {A}))\) . On the other hand, if
\(1 \in \theta (L(\mathcal {A}))\) , then there exists a path in \(\mathcal {A}\)  of the form
\(q_0 = s_0 \xrightarrow{} s_1 \xrightarrow{} s_2 \cdots s_{k-1} \xrightarrow{} s_k = q_f\) 
such that \(\theta (a_1 a_2 \cdots a_k) = 1\) . Let \((s_{j-1},a_j,s_j) = t_{i_j}\) , where we refer to the above enumeration of all transitions.
Then, we must have \(i_1 \le i_2 \le \cdots \le i_k\) . Moreover, we have
\(\theta (\widetilde{q_0}\, \widetilde{q_f}^{-1}) = \theta (\widetilde{q_0} \, a_1 a_2 \cdots a_k \, \widetilde{q_f}^{-1}) = \theta (\tilde{t}_{i_1} \tilde{t}_{i_2} \cdots \tilde{t}_{i_k})\in \theta ( \tilde{t}_1^*\, \tilde{t}_2^* \cdots \tilde{t}_m^*).\) 
This proves the claim and hence the theorem.
Theorem 7.4 Let \((A,I)\)  be an independence alphabet, which is not a transitive forest. Then,
knapsack for the graph group \(\mathbb {G}(A,I)\)  is NP-complete.

If \((A,I)\)  is not a transitive forest, then \(\mathsf {P4}\)  or \(\mathsf {C4}\)  is an induced subgraph of \((A,I)\)  [22]}.
Thus, \(\mathbb {G}(\mathsf {P4})\)  or \(\mathbb {G}(\mathsf {C4}) \cong F_2 \times F_2\)  is a subgroup of \(\mathbb {G}(A,I)\) . Hence,
NP-hardness of knapsack for \(\mathbb {G}(A,I)\)  follows from [6]} or Lemma REF .

Open problems
Our proof for the NP-completeness of knapsack for \(\mathbb {G}(A,I)\)  if \((A,I)\)  is not a transitive forest makes use of solutions with
exponentially large values for exponent variables. As a consequence, we cannot adapt our proof to the subset sum problem.
For \(\mathbb {G}(\mathsf {C4}) \cong F_2 \times F_2\)  we have shown in [6]} that the subset sum problem is NP-complete.
But for \(\mathbb {G}(\mathsf {P4})\)  it remains open whether subset sum is NP-complete.
Recall from Remark REF  that the knapsack variant, where we ask for a solution in \(\mathbb {Z}^k\)  (let us call this variant
integer-valued knapsack) can be reduced to our version of knapsack,
where the solution is restricted to \(\mathbb {N}^k\) . Hence, there might be groups where integer-valued knapsack is easier than
standard knapsack. Indeed, in the introduction we remarked
that integer-valued knapsack for the group \(\mathbb {Z}\)  with binary encoded integers
can be solved in polynomial time. This motivates the investigation of integer-valued knapsack for other
graph groups. In [6]} we proved that integer-valued knapsack for \(\mathbb {G}(\mathsf {C4})\)  is NP-complete,
even if group elements are given by uncompressed words. On the other hand, our NP-hardness proof for \(\mathbb {G}(\mathsf {P4})\) 
makes essential use of the fact that solution vectors are restricted to \(\mathbb {N}^k\) , and it remains open whether integer-valued knapsack for
\(\mathbb {G}(\mathsf {P4})\)  is NP-hard. In this context, it is interesting to note that there are some interesting differences between
\(\mathbb {G}(\mathsf {P4})\)  and \(\mathbb {G}(\mathsf {C4})\)  with respect to algorithmic problems. For instance, whereas the subgroup membership
problem for \(\mathbb {G}(\mathsf {C4})\)  is undecidable [26]}, the subgroup membership problem for \(\mathbb {G}(\mathsf {P4})\)  (and any graph group
\(\mathbb {G}(\Gamma )\)  with \(\Gamma \)  chordal) is decidable [27]}, [28]}.
As remarked in the introduction, there are nilpotent groups with an undecidable
knapsack problem. If a nilpotent group is an automatic group, then it must be virtually abelian [29]}.
This raises the question whether knapsack is decidable for every automatic group.
