# The Edit Distance to k-Subsequence Universality

arXiv: https://arxiv.org/abs/2007.09192 · HTML: https://mlsanity.com/paper/2007.09192/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2020.

## Built on by (most cited first, 4 of 4)

- [Scattered Factor Universality -- The Power of the Remainder](https://mlsanity.com/paper/2104.09063/) (2021)
- [m-Nearly k-Universal Words -- Investigating Simon Congruence](https://mlsanity.com/paper/2202.07981/) (2022)
- [α-β-Factorization and the Binary Case of Simon's Congruence](https://mlsanity.com/paper/2306.14192/) (2023)
- [Directed Regular and Context-Free Languages](https://mlsanity.com/paper/2401.07106/) (2024)

## Abstract (arXiv)

A word u is a subsequence of another word w if u can be obtained from w by deleting some of its letters. The word w with alph(w)=Sigma is called k-subsequence universal if the set of subsequences of length k of w contains all possible words of length k over Sigma. We propose a series of efficient algorithms computing the minimal number of edit operations (insertion, deletion, substitution) one needs to apply to a given word in order to reach the set of k-subsequence universal words.