On the shuffle of star-free languages (Q2893297)

The shuffle of two words \(u\) and \(v\) is defined as the set of all words \(u_1v_1u_2v_2\dots u_kv_k\), where \(k\geq 1\), \(u_1u_2\dots u_k = u\) and \(v_1v_2\dots v_k = v\), and the operation is extended to a language operation in the natural way. In this paper, the authors consider some topics related to the question of when the shuffle of two star-free languages is star-free. Firstly, they show that the family of star-free languages is closed under a restricted shuffle operation, and that the shuffle of two star-free languages is star-free if the languages are recognized by aperiodic monoids in which every \(D\)-class is a subsemigroup. Secondly, they discuss some special cases concerning languages that are submonoids generated by just one word as well as a couple of related problems concerning primitive words.