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 L⊢ I ∈, u ⊢I* v if and only if v is the shuffle of u and another word of L L⊢ I ∈ In [3], the authors have stated the problem of the characterization of the finite sets I such that ⊢I* is a well quasi-order on L L ⊢ I ∈. In this paper we give the answer in the case when I consists of a single word w. © Springer-Verlag Berlin Heidelberg 2006.
Well quasi orders and the shuffle closure of finite sets / D'Alessandro, Flavio; Gwenael, Richomme; Stefano, Varricchio. - STAMPA. - 4036 LNCS:(2006), pp. 260-269. (Intervento presentato al convegno 10th International Conference on Developments in Language Theory, DLT 2006 tenutosi a Santa Barbara, CA) [10.1007/11779148_24].
Well quasi orders and the shuffle closure of finite sets
D'ALESSANDRO, Flavio;
2006
Abstract
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 L⊢ I ∈, u ⊢I* v if and only if v is the shuffle of u and another word of L L⊢ I ∈ In [3], the authors have stated the problem of the characterization of the finite sets I such that ⊢I* is a well quasi-order on L L ⊢ I ∈. In this paper we give the answer in the case when I consists of a single word w. © Springer-Verlag Berlin Heidelberg 2006.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
