Well quasi-orders generated by a word-shuffle rewriting
Given a set I of words, the set L-proves(epsilon), of all words obtained by the shuffle of (copies of) words of I is naturally provided with a partial order: for it, v in L-proves(epsilon) u proves(I)* v if and only if v is the shuffle of u and another word of L-proves I(epsilon). 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 In this paper we give an answer in the case when I-proves I* characterization of the finite sets L-proves I(epsilon) such that is a well quasi-order on I consists of a single word w. (c) 2007 Elsevier B.V. All rights reserved.
well quasi-orders shuffle formal languages