Consider the following game between *Alice* and *Bob*.
$\Sigma$ is a finite nonempty alphabet, $\Delta \notin \Sigma$ denotes
a special symbol, and $k > 0$ is a positive integer constant representing
the length of contexts.

*Alice*gets a message $w \in \Sigma^{\omega}$. She then finds an appropriate index $i > k$ and passes the following message: $w[i - k \ldots i - 1]\ \Delta\ w[i + 1 \ldots i + k]$ to Bob.*Bob*receives the message $l\ \Delta\ r$, where $l, r \in \Sigma^k$. Based on the context $(l, r)$ he then recovers the original hidden letter $w[i]$.

The question is, whether there exists any such protocol enabling the above game? Is it possible for Alice to always find an appropriate index $i$, such that Bob is then able to recover the hidden letter?

## Background/Motivation

If such protocol existed it would enable to encode any information into a sufficiently long word only by means of replacing appropriate letters by the $\Delta$ symbol. It would be also possible to recover the original word only by looking at the limited context surrounding these $\Delta$ symbols.

Similar, but a little more involved coding was used in our paper:

P. Cerno, F. Mraz: *Delta-Clearing Restarting Automata and CFL*,
Proceedings of the DLT 2011 15th International Conference on Developments in Language Theory (Milano, Italy), Springer, Berlin, 2011, LNCS, Vol. 6795, 153-164.

## Partial Solution

I was able to find a correct protocol only for a two-letter alphabet.

Let $\Sigma = \{a, b\}$. Then there exist integers $B, k > 0$, and a table $T$ of triples $(x, z, y)$, $x, y \in \Sigma^k$, $z \in \Sigma$, such that:

- For each context $(x, y) \in \Sigma^k \times \Sigma^k$ there exists at most one $(x, z, y) \in T$.
- For each $w \in \Sigma^B$ there exists at least one $(x, z, y) \in T$, such that $xzy$ is a subword of $w$.

*Proof*.
Let us set $B = 8$, $k = 2$, and $T$ to be the following set:

```
{(aa, a, aa), (ab, a, aa), (ba, b, aa), (bb, a, aa),
(aa, a, ab), (ab, a, ab), (ba, b, ab), (bb, a, ab),
(aa, b, ba), (ab, a, ba), (ba, b, ba), (bb, b, ba),
(aa, b, bb), (ab, a, bb), (ba, b, bb), (bb, b, bb)}
```

Note that $T$ can be shortly described as $T = \{ (xx, y, y?) \} \cup \{ (xy, x, ??) \mid x \neq y \}$, where $x, y \in \{a, b\}$, and the symbol $?$ represents an arbitrary letter.

The intuition why this works is following: Consider a sufficiently long word $w \in \{a, b\}^*$. Then there are only two cases: either each (internal) letter in $w$ is doubled, i.e. each (internal) letter $x$ in $w$ has a neighbor $x$, or there exists an (internal) letter $x$ in $w$ which does not have a neighbor $x$. In the first case the pattern $xxyy$ will occur, and in the second case the pattern $xyx$, where $x \neq y$, will occur.

The question is, whether there are similar protocols also for larger alphabets?