Additional Problem 1: Short Distinguishing Subsequence
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
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,
The Design and Analysis of Computer Algorithms,
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.