The String-to-String Correction Problem

In this paper, we consider the problem of constructing a shortest string of {1,2,...,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less ...

For every string inclusion relation there are two optimization problems: find a longest string included in every string of a given finite language, and find a shortest string including every string of a given finite language. As an example, the two well-...

An indeterminate string (or, more simply, just a string) x = x 1 . . n ] on an alphabet Σ is a sequence of nonempty subsets of Σ. We say that x i 1 ] and x i 2 ] match (written x i 1 ] x i 2 ] ) if and only if x i 1 ] x i 2 ] . A feasible array is an ...