Avoidable sets and well quasi orders
Flavio D’Alessandro, VARRICCHIO S. · IRIS Research product catalog (Sapienza University of Rome) · 2004
Let I be a finite set of words and ⇒I* be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let LI ε be the set of words u such that ε ⇒I* u. We prove that the set I is unavoidable if and only if the relation ⇒I* is a well quasi-order on the set LI ε. This result generalizes a theorem of [7]. Further generalizations are investigated. © Springer-Verlag Berlin Heidelberg 2004.