Given a set I of words, the set L⊢Iε{lunate} 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ε{lunate}, u ⊢I* v if and only if v is the shuffle of u and another word of L⊢Iε{lunate}. 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ε{lunate}. In this paper we give an answer in the case when I consists of a single word w. © 2007 Elsevier Ltd. All rights reserved.
Well quasi-orders generated by a word-shuffle rewriting / D'Alessandro, Flavio; Richomme, G; Varricchio, S.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 377:(2007), pp. 73-92. [10.1016/j.tcs.2007.02.007]
Well quasi-orders generated by a word-shuffle rewriting
D'ALESSANDRO, Flavio;
2007
Abstract
Given a set I of words, the set L⊢Iε{lunate} 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ε{lunate}, u ⊢I* v if and only if v is the shuffle of u and another word of L⊢Iε{lunate}. 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ε{lunate}. In this paper we give an answer in the case when I consists of a single word w. © 2007 Elsevier Ltd. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
