Sequences of Lyndon Words

L. J. Cummings
Additional contact information
L. J. Cummings: University of Waterloo

A chapter in Sequences, 1990, pp 156-165 from Springer

Abstract: Abstract 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.

Keywords: Block Code; Lexicographical Order; Cyclic Permutation; Gray Code; Binary Case (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_12

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().