The Edit Distance to k-Subsequence Universality
Joel D. Day, Pamela Fleischmann, Maria Kosche, Tore Koß, Florín Manea, Stefan Siemer · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
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.