7 - Circular codes

Summary

In this chapter we study a particular family of codes called circular codes. The main feature of these codes is that they define a unique factorization of words written on a circle. The family of circular codes has numerous interesting properties. They appear in many problems of combinatorics on words, several of which will be mentioned here.

In Section 7.1 we give the definition of circular codes and we characterize the submonoid generated by a circular code. We also describe some elementary properties of circular codes. In particular we characterize maximal circular codes (Theorem 7.1.10).

In Section 7.2 we introduce successive refinements of the notion of a circular code. For this we define the notion of (p, q)-limitedness. We then proceed to a more detailed study of (1, 0)-limited codes. In particular, we show (Proposition 7.2.10) that (1, 0)-limited codes correspond to ordered automata. Comma-free codes are defined as circular codes satisfying the strongest possible condition.

Section 7.3 is concerned with length distributions of circular codes. Two important theorems are proved. The first gives a characterization of sequences of integers which are the length distribution of a circular code (Theorem 7.3.7). The second shows that for each odd integer n there exists a system of representatives of conjugacy classes of primitive words of length n which not only is circular but even comma-free (Theorem 7.3.11). The proofs of these results use similar combinatorial constructions. As a matter of fact they are based on the notion of factorization of free monoids studied in Chapter 8.