In [G.Kucherov and M.Rusinowitch, Undecidability of ground
reducibility for word rewriting systems with variables, Information
Processing Letters, 53:209--215, 1995]
we proved that for a word rewriting system
with variables $\R$ and a word
with variables $w$, it is undecidable if $w$ is ground reducible
by $\R$, that is if all the instances of
$w$ obtained by substituting its variables by non-empty words
are reducible by $\R$. On the other hand, if $\R$ is linear, the question
is decidable for
arbitrary (linear or non-linear) $w$. In
this paper we futher study the complexity of the above problem and prove
that it is {\it co-NP}-complete if both $\R$ and $w$ are restricted to be
linear. The proof is based on
the construction of a deterministic finite automaton for the language
of words reducible by $\R$. The construction generalizes the well-known
Aho-Corasick automaton for string matching against a set of keywords.