Well quasi-orders generated by a word-shuffle rewriting

摘要

Given a set I of words, the set LεI of all words obtained by the shuffle of (copies of) words of I is naturally provided with a partial order: for u,v in LεI, u*I if and only if v is the shuffle of u and another word of LεI. In [F. D’Alessandro, S. Varricchio, Well quasi-orders, unavoidable sets and derivation systems, in: Word Avoidability Complexity and Morphisms (WACAM), RAIRO Theoretical Informatics and Applications 40 (3) (2006) 407–426 (special issue)], the authors have opened the problem of the characterization of the finite sets I such that *I is a well quasi-order on LεI. In this paper we give an answer in the case when I consists of a single word w.