Additional Problem 1: Short Distinguishing Subsequence

$$\def\SMot{\mathit{Subs}}$$

The problem consider distinguishing subsequence between two different binary words (see Problem 51). Denoting by $\SMot(x)$ the set of subsequences of a word $x$, a word $z$ is said to distinguish $x$ and $y$, $x\neq y$, if it is a subsequence of only one of them, that is, $z\in \SMot(x)\Leftrightarrow z\notin \SMot(y)$.

Construct a distinguishing subsequence of length at most $\lceil (n+1)/2 \rceil$ for two distinct binary words of the same length $n$.

In fact, the above bound is optimal.

For each $n\gt 0$, construct two distinct binary words of length $n$ that do not have a distinguishing subsequence of length smaller than $\lceil (n+1)/2 \rceil$.

References

• A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
• P. Gawrychowski, M. Kosche, T. Koÿ, F. Manea, and S. Siemer, Efficiently testing Simon's congruence, In M. Bläser and B. Monmege, editors, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 34:1-34:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.