Picture codes and deciphering delay (Q515672)

In this paper, the authors introduce some families of two-dimensional languages having unique decomposition properties. A \textit{picture} \(p\) over a finite alphabet \(\Sigma\) is a two-dimensional rectangular array of elements of \(\Sigma\). The set of all pictures over \(\Sigma\) is denoted by \(\Sigma^{**}\) and a \textit{picture language} over \(\Sigma\) is just a subset of \(\Sigma^{**}\). A picture language \(X\) of pictures over \(\Sigma\) is a called a \textit{code} if any picture over \(\Sigma\) is tilable (using polyominoes) in at most one way with elements in \(X\). The problem whether a given set of pictures is a code is in general undecidable, even if the set is finite. A \textit{prefix code} is a set \(X\) such that during the decoding process of a picture obtained using only elements of \(X\), the next element (once having fixed a scanning direction, e.g., from the top-left corner towards the bottom-right one) in \(X\) is uniquely determined. Every prefix set of a picture is a code and the family of finite prefix codes has the important property of being decidable. Moreover, there is a polynomial decoding algorithm for a finite prefix picture code. In this paper, a \(2\)-dimensional notion of deciphering delay is introduced and it is proved that picture codes with deciphering delay \(k\) form a decidable class of picture codes. Codes with finite deciphering delay form an intermediate family between prefix codes and general codes. Intuitively, the \textit{delay} \(d\) of a set is the amount of code words that are necessary to scan in the coded message before the first one can be determined. The smallest integer \(d>0\) satisfying the condition is the \textit{deciphering delay} of \(S\). Deciphering delay equal to \(k \geq 1\) means that we can possibly begin two candidate decompositions that differ in the first picture, only if the smallest contains \textit{up to} \(k\) code pictures: if we add further code pictures, only one of the attempts of decomposition can survive. If a (finite or infinite) set of pictures has a finite deciphering delay, then it is a code. The pictures with delay \(0\) correspond to the prefix sets. One of the main results is that it is decidable whether a finite set of pictures has deciphering delay \(k \geq 0\). Another important result is that the set of pictures having finite deciphering delay are codes. This result holds both for finite and infinite picture languages. Hence, it provides a useful tool to prove that a picture language is a code (while this property is in general undecidable). Further, the authors exhibit, for each integer \(k\), a set with deciphering delay equal to \(k\), and indicate a set that does not have finite deciphering delay.