The edit distance to k-subsequence universality

A word u is a subsequence of another word w if u is obtained from w by deleting some of its letters. In the 1970s, Simon defined the relation ∼k (called now Simon-Congruence) as follows: two words having the same set of subsequences of length k are ∼k-congruent. It is thus natural to ask, for non k-equivalent words w and u, what is the minimal number of edit operations that we need to perform on w to obtain a word which is ∼k-equivalent to u. Here, we consider this problem in a specific setting: when u is a k-subsequence universal word. A word u with alph(u)=Σ is called k-subsequence universal if the set of length-k subsequences of u contains all possible words of length k over Σ. As such, our results are a series of efficient algorithms computing the edit distance from w to the language of k-subsequence universal words.