Two-Word Shuffle: Some Results

Abstract

In this paper, we study the shuffle operator on two words. First, we give a combinatorial analysis of the number of distinct languages generated by such shuffle operations, relying on known results that ensure their uniqueness. We establish a bijection between two-word shuffles and initial segments of natural numbers, enabling the enumeration and a natural uniform random generation of shuffle languages. As the shuffle of two words corresponds to a language where all the words have the same length, a block language, we show how to inductively construct its bitmap representation. We then turn our attention to both deterministic and nondeterministic state complexity of the shuffle square of a word, i.e., the shuffle of a word with itself. Finally, we examine the average state complexity of the partial derivative automata for the two-word shuffle.