string, set m to 1 and k to 0 so that they point to the second and the first symbol of the string respectively. When m > N, it is essentially the same as encountering minus infinity, thus, add the first m-k collected symbols to the result list after removing them from the string, set m to 1 and k to 0, and return to the previous step. Add S to the result list. Connection to de Bruijn sequences If one concatenates together, in lexicographic order, all the Lyndon words that have length dividing a given number n, the result is a de Bruijn sequence, a circular sequence of symbols such that each possible length-n sequence appears exactly once as one of its contiguous subsequences. For example, the concatenation of the binary Lyndon words whose length divides four is 0 0001 0011 01 0111 1 This construction, together with the efficient generation of Lyndon words, provides an efficient method for constructing a particular de Bruijn sequence in linear time and logarithmic space. Additional properties and applications Lyndon words have an application to the description of free Lie algebras, in constructing a basis for the homogeneous part of a given degree; this was Lyndon's original motivation for introducing these words. Lyndon words may be understood as a special case of Hall sets. For prime p, the number of irreducible monic polynomials of degree d over the field is the same as the number of Lyndon words of length d in an alphabet of p symbols; they can be placed into explicit correspondence. A theorem of Radford states that a shuffle algebra over a field of characteristic 0 can be viewed as a polynomial algebra over the Lyndon words. More precisely, let A be an alphabet, let k be a field of characteristic 0 (or, more general, a commutative -algebra), and let R be the free noncommutative k-algebra . The words over A can then be identified with the "noncommutative monomials" (i.e., products of the xa) in R; namely, we identify a word (a1,a2,...,an) with the monomial xa1xa2...xan. Thus, the words over A form a k-vector space basis of R. Then, a shuffle product is defined on R; this is a k-bilinear, associative and commutative product, which is denoted by ш, and which on the words can be recursively defined by 1 ш v = v for any word v; u ш