Maximal Prefix-Synchronized Codes
Leonidas Guibas, Andrew M. Odlyzko · SIAM Journal on Applied Mathematics · 1978
A prefix-synchronized code with prefix P of length p is a collection of strings whose first p characters equal P, but which have the property that P does not occur in any concatenation of codewords in any positions but those corresponding to initial segments of codewords. Given a block length N and the size q of the alphabet, it is desirable to find prefixes which maximize the size of the code. Gilbert conjectured that if $q = 2$, some maximal prefix-synchronized codes have prefixes of the form $11 \ldots 10$ for a suitable length p. It is shown here that this conjecture is true (at least for large N) for $q = 2$, as well as $q = 3$ and $q = 4$, but that it is false for $q \geqq 5$. It is also shown that the sizes of maximal prefix-synchronized codes exhibit some rather interesting oscillations as the block length increases. The proofs involve combinatorial arguments to establish closed form expressions for generating functions as well as extensive analysis of those generating functions.