On the Descriptional Complexity of Literal Shuffle

Abstract

In this paper, we study the descriptional complexity of several variants of the shuffle operation on regular languages. In the perfect shuffle, words of equal length strictly alternate their symbols. If the words have different lengths, the initial literal shuffle performs the perfect shuffle while both words have symbols and then appends the remaining suffix of the longest word. Lastly, the literal shuffle is an extension of the previous operation, in which the initial shuffle may start at an arbitrary position in one of the two words. We analyze the number of states sufficient and necessary for nondeterministic and deterministic automata to recognize the resulting languages. For nondeterministic finite automata, the cost of the simulation is polynomial. In the worst case, a deterministic finite automaton requires exponentially many states to recognize the literal shuffle of two languages given also by deterministic finite automata, whereas a deterministic.1-limited automatonnamely, a one-tape Turing machine in which each cell may be rewritten only upon its first visit requires only polynomial many states. (c) The Author(s).