Shuffle and scattered deletion closure of languages
We 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. (C) 2000 Elsevier Science B.V. All rights reserved.
shuffle residual shuffle closure insertion and deletion operations shuffle operation maximal shuffle residual rss-type laguage