Index Terms
- String wars
Recommendations
Shortest string containing all permutations
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 ...
String Noninclusion Optimization Problems
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-...
Inferring an indeterminate string from a prefix graph
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 ...
Comments