's parsing algorithm is exponential in k. The translation we just sketched uses s source names.
we see that a HRG with rules of tree-width ≤ k can be encoded into an s-graph grammar with k + 1 source names.