Published online by Cambridge University Press: 18 October 2006
Let I be a finite set of words and $\Rightarrow_I^*$ be the derivation relation
generated by the set of productions {ε → u | u ∈ I}.
Let $L_I^{\epsilon}$
be the set of words u such that $\epsilon \Rightarrow_I^* u$
.
We prove that the set I is unavoidable if and only if the relation $\Rightarrow_I^*$
is a well quasi-order on the set $L_I^{\epsilon}$
. This result generalizes a theorem of
[Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.