Summary: [For the entire collection see Zbl 0685.00004.]
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, \(\Lambda_ 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 \(\Lambda_ 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 \(\Lambda_ 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 \(\Lambda_ n\). We show that the existence of a sequence of length m for some subset of \(\Lambda_ k\), yields a construction for a sequence of \(r(m-1)+s\) edges in \(\Lambda_{rk+s}\) for each pair of positive integers r,s\(\geq 1\). We further show the existence of a cycle in \(\Lambda_ k\) permits the construction of a cycle in \(\Lambda_{rk+s}\) of length mr for each pair of positive integers r,s\(\geq 1\). In addition, a sequence in an earlier \(\Lambda_ k\) can, under certain conditions, lead to a construction of a cycle in a \(\Lambda_ n\) with \(n>k\).