Advanced Search

Let be a finite set of words and ${\Rightarrow }_I^{*}$ be the derivation relation generated by the set of productions {}. Let $L_I^{ϵ}$ be the set of words such that $ϵ{\Rightarrow }_I^{*}u$. We prove that the set is unavoidable if and only if the relation ${\Rightarrow }_I^{*}$ is a well quasi-order on the set $L_I^{ϵ}$. This result generalizes a theorem of [Ehrenfeucht (1983) 311–332]. Further generalizations are investigated.