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.


1. *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.
2. *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:


1. For each context $(x, y) \in \Sigma^k \times \Sigma^k$ there exists 
at most one $(x, z, y) \in T$.
2. 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?
> 
> 
> 



Can you hide a letter without losing information?
We say that Alice catches the word if she can make the desired move. We prove that a protocol exists by the induction on $d=|\Sigma|$.


Your example states the base for $d=2$. Assume that we know Alice's strategy for $d-1$ letters; let $k'$ be the length of the words in the catching triples. Note that in fact Alice catches all the finite words of some length $N'$; otherwise by Koenig's lemma there exists an infinite word which is not caught. 


We may assume that $k'\geq 2d$. Now fill an alphabet with $d$th letter $x$. We claim that we can set $k=N'$. 


We will use the "catching words" of length $\leq k$ instead of exactly $k$; this means that we extend all the left words by arbitrary letters from the left, and all right words --- to the right to obtain the words of desired length. 


0) First, take all Alice's words for the alphabet $\Sigma\setminus\{x\}$. Then she will catch any word which contains a subword of length $N'$ not containing $x$ (this subword should stand far enough from the beginning of the word). 


We say that a word is valid if it does not contain $x$. 
Now we need to catch all other words; they consist of subwords of the form $xWx$, where $0\leq |W|\leq N'$, and $W$ is a valid word (these subwords overlap by letters $x$). We will consider only the words $W$ standing far enough from the beginning. 


We distinguish three cases: 1) maximal length of $W$ is at least $2d$; 2) this maximal length is in $[d,2d-1)$, and 3) this maximal length is less than $d$.


To catch 1), assign to each $a\in \Sigma$ its value $\nu(a)$ from 1 to $d$ bijectively; let $\nu(W)$ be the sum of values of letters of $W$ (with repetitions) modulo $d$.
Now we use the catching triples of the form $(xU,a,Vx)$ where $U,V$ are valid, $0\leq |U|\leq d-1$, $d\leq |V|\leq N'$, $2d-1\leq |U|+|V|\leq N'-1$, and $\nu(UaV)=|U|$. Now, if we have the subword $xWx$ with $|W|\geq 2d$, then we set $U$ to be the beginning of $W$ of length $\nu(W)$, $a$ to be the next letter of $W$, and $V$ to be the remaining tail. Our word is caught since $a$ is determined uniquely by $U$ and $V$.


To catch 2), we choose the pairs of the form $(xU,x,?)$ where $d\leq |U|\leq 2d-1$ and $U$ is a valid word. 


Finally, to catch 3), we take all the triples of the form $(xU,x,Vx)$ where $0\leq |U|,|V|\leq d-1$, and $U,V$ are valid words.


It is easy to note that our triples do not contradict to each other. To see this, in each triple consider the tails $L\_d$ and $L\_{2d}$ of the left word and the beginnings $R\_d$ and $R\_{2d}$ of the right word, of lengths $d$ and $2d$ respectively; recall that $k'\geq 2d$. In 0), $L\_{2d}$ does not contain $x$. In 2), $L\_{2d}$ contains $x$, while $L\_d$ does not. In 1), $L\_d$ contains $x$ while $R\_d$ does not. Finally, in 3) both $L\_d$ and $R\_d$ contain $x$.


So, the algorithm for Bob is as following. By the rules above, he determines which type of triple he has received. In 0), he finds the letter by the algorithm for $d-1$ letters; in 2) and 3), he simply answers $x$. In 1), he determines $U$ and $V$ (as the longest tail and beginning not containing $x$) and then finds $a$ from the condition $\nu(UaV)=U$.


