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 [1]},
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 [1]} 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 [1]} 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.
