Appendix: Research problems

Summary

In this appendix, we gather, for the convenience of the reader, the conjectures mentioned in the book and present some additional open problems. We take this opportunity to discuss some of them in more detail.

The inclusion problem Recall from Chapter 2 that the inclusion problem for a finite code X is the existence of a finite maximal code containing X. The inclusion conjecture is that this problem is decidable.

The smallest integer k for which a k element code is known which is not included in a finite maximal code is k = 4. Such an example is the code X = ﹛a⁵, ba², ab, b﹜ of Example 2.5.7. Proposition 12.3.3 describes an infinite family of codes to which X belongs. It is not known whether every code with three elements is included in a finite maximal code.

For a finite bifix code X, the existence of a finite maximal bifix code containing X is decidable. Indeed, if X is insufficient, then any maximal bifix code with kernel X is finite by Proposition 6.5.6. On the contrary, if X is sufficient, then the degree of a finite maximal code containing X must be equal to the common value (L_X,w) of the indicator L_X of X for any full word w whose length exceeds the maximal length of the words of X. Since there is a finite number of finite maximal bifix codes with given degree, this gives a decision procedure (although it is not a very practical one).