Shuffles and Synchronized Shuffles: A Survey

Summary. We present an overview of different approaches to define shuffles and synchro-nized shuffles of words. The shuffle operations considered are distinguished by conditions according to which certain occurrences of symbols common to the original words may or must be identified (synchronized). The words that are shuffled may be infinite which leads to the possibility of unfair shuffling. In addition to illustrating the conceptual differences, we survey and extend known results. “Our conclusion is, in brief, that shuffling is complex.” Ogden, Riddle, and Round in [27], POPL’78