Sequences of Lyndon Words

A code has bounded synchronization delay if there exists an integer s such that at most s consecutive bits are required to establish word synchronization in any message. The set of Lyndon words of length n, Λ n , is the set obtained by choosing those strings which are lexicographically least in the primitive equivalence classes determined by cyclic permutation. We give an elementary proof that Λ n is a maximal code with bounded synchronization delay for fixed word length n. For any finite alphabet A, the n-cube over A is the set of strings A n viewed as a graph in which the vertices are the strings of length n. Two such vertices are adjacent if they differ in exactly one position. Any code of fixed word length n can be represented as a set of vertices in the n-cube. It is known that the code Λ n is a connected subset of the n-cube in the binary case. A sequence or path in the n-cube is a listing of a set of vertices in the cube without repetition in such a way that each vertex of the list differs in only one bit from the adjacent vertices. Although techniques are known for constructing sequences of all vertices of the n-cube (sometimes called a Gray code), it is often difficult to find such a listing for a particular subset of the n-cube such as Λ n . We show that the existence of a sequence of length m for some subset of Λ k , yields a construction for a sequence of r(m— 1)+s edges in Λrk+sfor each pair positive integers r,s ≥1. We further show the existence of a cycle in Λ k permits the construction of a cycle in Λrk+s of length mr for each pair of positive integers r,s ≥1. In addition, a sequence in an earlier Λ k can, under certain conditions, lead to a construction of a cycle in a Λ n with n > k.