Can you hide a letter without losing information?

Question

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?

Answer 1

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$.

Answer 2

This is just a thought, and I am going to re-check I have understood the problem first: Your protocol (binary solution) works because in $T$ the triples $(x, z, y)$ appear with every combination of $x$ and $y$ exactly once and because for every $w \in \Sigma^8$ there exists an element of $T$ such that $w$ contains at least one $xzy$ as a substring. So if $z$ is replaced by $\Delta$ then $w$ contains $x \Delta y$ and so $x \Delta y$ uniquely defines $\Delta$ as $z$ for a triple $(x, z, y) \in T$.

And you're claiming that this is extended beyond $k = 2$.

So assuming I understand that correctly, what you need to make it work for bigger alphabets, is again a table $T$ consisting of triples $(x, z, y)$, with $x, y \in \Sigma^k$ where every combination of $x$ and $y$ occur, and for some $B(k)$ every $w \in \Sigma^{B(k)}$ contains some $xzy$ as a substring. Then there should be some Ramsey style theorem to find $B(k)$. Can you clarify why your original method doesn't extend to larger alphabets?

Another thought is if you can create a table $T$ for any $k$ with $\mid \Sigma \mid = 2$, then for $ \mid \Sigma'\mid = 2^n$ and $k'$ why don't you take $k = n k'$ and then generate $T$,and $T$ contains triples $(x, z, y)$ such that every combination of $x$ and $y$ occurs with a unique $z$ in between, then each $x \in \Sigma^{k}$ is equivalent to an $x' \in \Sigma'^{k'}$ as $k = nk'$. You actually can replace a 'short string' if this works,ie. of length $n$. I'm not 100% sure if this actually works, but I think if you increase $B$ then the substring relation should still hold.