Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
Can you give some more background - why is this particular encoding scheme interesting to study? –  Marcin Kotowski Sep 25 '11 at 15:41
1  
Hi, thank you for asking, my area of research includes the theory of automata and formal languages. I have been studying one very restricted model for accepting formal languages: the so-called delta-clearing restarting automaton, which can, based on a limited context, either delete a substring of the tape, or replace a substring by a special auxiliary symbol Delta. This model is partially linguistically motivated, but also has some other interesting properties. For more information, please visit my homepage. The above coding could prove very useful for this (or similar) models. –  Cerno Sep 25 '11 at 17:08
    
Related (but not equivalent) is the card trick mathoverflow.net/questions/9754/… –  Zsbán Ambrus Jun 12 '13 at 9:12

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
Wow, thank you very much for your excellent answer. I have checked your proof for several times, but I was not able to find any "catch". It seems that your proof is correct. Thank you. –  Cerno Sep 26 '11 at 20:31

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.

share|improve this answer
    
Thank you for your answer, you seem to perfectly understand my solution and the problem as well. It is true, that in my solution (for two-letter alphabets) the triples (x, z, y) appear with every combination of x and y exactly once, but this is not necessary. In this problem, the second condition is a really important one (and nontrivial to achieve). It is also true, that the contexts in T could be easily prolonged. But I am afraid your proposed solution does not work. It is not enough to just encode bigger alphabets to the binary alphabet, because the reverse process will not work. –  Cerno Sep 25 '11 at 17:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.