The Frobenius problem for the shuffle operation

2016/08/30 by Jeremy Nicholson, Narad Rampersad, Nicholson, Jeremy +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL

paper · pdf · doi:10.48550/arxiv.1608.08592

16 pages

arxiv created 2016/08/30 · arxiv updated 2016/08/31

Abstract

We characterize the finite sets S of words such that that the iterated shuffle of S is co-finite and we give some bounds on the length of a longest word not in the iterated shuffle of S.

Related

• Infinite square-free self-shuffling words
• Square-Free Shuffles of Words
• The Frobenius problem for homomorphic embeddings of languages into the integers
• Asymptotically half of binary words are shuffle squares
• Well quasi-orders and the shuffle closure of finite sets