Well quasi-orders, unavoidable sets, and derivation systems
Flavio D’Alessandro, Stefano Varricchio · RAIRO - Theoretical Informatics and Applications · 2006
Let I be a finite set of words and be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let be the set of words u such that . We prove that the set I is unavoidable if and only if the relation is a well quasi-order on the set . This result generalizes a theorem of [Ehrenfeucht et al., Theor. Comput. Sci. 27 (1983) 311–332]. Further generalizations are investigated.