Shuffle and scattered deletion closure of languages

AbstractWe introduce and study the notion of shuffle residual of a language L: the set containing the words whose shuffle with L is completely included in L. Several properties and a characterization of the shuffle residual of a language are obtained. The shuffle closure of a language L (the smallest language that is shuffle closed and contains L) is investigated. Moreover, conditions for the existence of maximal languages whose shuffle residual equals a given language are obtained. The paper also considers an operation dual to shuffle, namely scattered deletion: the scattered deletion of a word w from u consists of the words obtained by sparsely deleting from u the letters of w, in the order in which they appear in w. The scattered deletion residual and scattered deletion closure of a language are defined and studied. Finally, relationships and interdependencies between shuffle, scattered deletion, and other insertion and deletion operations are obtained