Maximal codes with bounded deciphering delay (Q1177932)

A code has a bounded deciphering delay if, when reading from left to right, the deciphering of messages coded according to such codes, can already begin after a ``bounded'' delay, without waiting for the end of the message. \(D_ A(d)\) denotes the family of codes (over the alphabet \(A\)) with bounded deciphering delay equal to \(d\). This paper investigates such codes. It is organized in four sections, the first is an introduction. The basic notation and terminology is established in Section 2. In Section 3, the author studies the concept of maximality for codes with bounded deciphering delay. A combinatorial characterization of a code which is maximal in \(D_ A(d)\) is given (Theorem 3.2). For thin codes with bounded deciphering delay \(d\), the equivalence between maximal codes and codes maximal in \(D_ A(d)\) (Theorem 3.3) is shown. The main result is a procedure which embeds any code with a given bounded deciphering delay \(d\) into a maximal code in \(D_ A(d)\) (Theorem 4.7). This construction answers a question of \textit{J. Berstel} and \textit{D. Perrin} [Academic Press Orlando etc. (1985; Zbl 0587.68066)]. Moreover this procedure gives rise to an algorithm that includes, in a finite number of steps, each finite code with bounded deciphering delay into a maximal code which is regular and has the same deciphering delay.