Well quasi-orders and the shuffle closure of finite sets

2006/07/18 by Flavio D'Alessandro, D'Alessandro, Flavio, Gwénaël Richomme +3
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0607082

arxiv created 2006/07/18 · arxiv updated 2016/08/16

Abstract

Given a set I of word, the set of all words obtained by the shuffle of (copies of) words of I is naturally provided with a partial order. In [FS05], the authors have opened the problem of the characterization of the finite sets I such that the order is a well quasi-order . In this paper we give an answer in the case when I consists of a single word w.

Related

• Well-Quasi-Orderings on Word Languages
• Atomicity and well quasi-order for consecutive orderings on words and permutations
• Well quasi-orders arising from finite ordered semigroups
• Set systems: order types, continuous nondeterministic deformations, and quasi-orders
• Well quasi-orders and the functional interpretation